Monotonicity

The events that Orchids receives and dissects are composed of fields.  In addition to a type, each field has a monotonicity status.

In each module page, we write ✓ in the `mono?’ column for fields that are monotonic.  Those are fields that can only increase (or stay the same), as new events occur.  The typical monotonic field is a time stamp or a sequence number.

The purpose of monotonicity

The monotonicity flag is used by Orchids to make a few important optimizations.  Some of them are described on the timeout module page.  If you write something like this in an Orchids rule:
expect (⟨what I am waiting for⟩ && ⟨my time field⟩<$timeout) goto⟨wherever⟩;

where $timeout holds the final time after which we will no longer care whether ⟨what I am waiting for⟩ happened or not, and ⟨my time field⟩ is flagged as a monotonic field, then Orchids will stop waiting after receiving the first event whose ⟨my time field⟩ field is larger than or equal to $timeout.  The way the Orchids compiler reasons is as follows: imagine Orchids receives an event whose ⟨my time field⟩ value is larger than or equal to $timeout; then any event it will read later will have an even larger ⟨my time field⟩, and the condition of the expect transition will be false forever.  Hence it makes no sense monitoring that condition, and we can kill the corresponding thread.

A matter of trust

Orchids trusts that monotonic fields indeed only increase, but some event sources may contradict that assumption.

If you see a monotonic field decrease, that may be the result of malevolent conduct.  That may happen in natural situations as well.  For example, if ⟨my time field⟩ reports times relative to a local time zone, and the time goes suddenly back from 3am to 2am in the middle of the night, it may be an effect of exiting daylight saving time.  The ideal cure is to have a time reporting mechanism that reports absolute values of time, not depending on a time zone or on daylight saving time, for example a Unix time count (numbers of seconds since a fixed date), or expressive and normalized time fields such as in RFC5424 syslog.

Beyond

In principle, fields can also be flagged as antitonic (decreasing or staying the same), or constant (staying the same).  This is needed by the logic that Orchids uses to reason about monotonicity.  At the moment, no field is flagged as such.

Monotonicity does not make sense for data of all types.  The order that Orchids uses is:

  • the natural ordering on data of types int, uint, float, ctime, timeval,
  • the lexicographic ordering on strings (of type str), seen as byte strings—not any fancier ordering such as UTF8 collation order: that may come, but no field of type str is currently flagged as monotonic anyway;
  • ipv4 addresses are compared as though they were unsigned 32-bit integers;
  • ipv6 addresses are compared lexicographically, considering they are 16-byte strings;
  • databases, of type db[*] or db[type1, …, typen], are compared for inclusion.