Friday, November 28, 2008

More on event hierarchies - cycles as hierachy spoiler

Yesterday I had the honor to eat dinner with the Israeli president Shimon Peres (well - not 1-1 dinner, not even in the same table, but on the table next to his); this was in an event that included many of the seniors of the Israeli High-Tech, about a project in which I am involved of helping Arabs to break into the Israeli high-Tech on which I have written before.

In Israel, the president is a symbolic head of state, while the "CEO" is the prime-minister; Shimon Peres, seen in this picture from last week where he became a knight by the UK queen, is a very impressive person, 85 years old who has a lot of energy and considered as the ultimate elder statesman. I wish that I'll have the same energy and vitality in the age of 58...

Back to event processing -- reflecting back on the "event hierarchy" discussion. Some people assume that the event processing network is a DAG (Directed Acyclic Graph) which is a structure whose handling is well-known, unfortunately, the world may be sometimes cyclic and the event processing network that represents this world is also cyclic.

Let's look at the following example -- I went to the interior ministry for re
This is, of course, an event processing system, relatively simple one. Trying to sketch the event processing network we'll have events - like:
customer arrived, clerk arrived, clerk displayed number, customer sits in front of clerk, customer gets up and leaves the clerk, clerk displays number.

Looking at this events we can realise that they create the following cycle
clerk arrived ; clerk displayed N; customer sits in front of clerk; customer leaves clerk; clerk displayed L etc... This is a cycle Clerk displayed L is an indirect descendant of Clerk displayed N... and likewise we need to continue circling...
Since event processing network deals with event types then we can say that "clerk displayed number" repeats itself, this may also be for the same clerk and same number -- same clerk, since clerk's id is fixed, same number -- since numbers can be recycled (e.g. after getting to 20, return to 1)... The support of cycles, of course, spoils the notion of hierarchy.

How do we know that cycle will not be infinite? ---- if the context is bounded then there is a natural stopper for the cycle (e.g. end of the reception hours), if the context is not bounded, then an infinite loop is possible, and there should be other means to detect and handle it, if occurs (e.g. allow limited number of cycles).

Should we forbid cycles? -- we are back to the dilemma about Russell's type theory.
we can forbid it and our language will be restricted and will not be able to express scenarios such as the one expressed in the example above, if we allow it --- we spoil the strict hierarchy, but as mentioned in the previous postings, strict hierarchy of events may not be realistic.


Nigel said...

Without supporting the hierarchical notion, I'd just like to point out that you are in danger of confusing events with states.

"The clerk displaying N" is a state (his display shows N). The clerk himself goes from "serving a customer" to "taking a tea break" to "waiting for a customer" and it is on the transition into the last state that the display is changed (we hope) - "the clerk displays N at 14.03" is the corresponding event.

A subsequent event "customer X approaches desk at 14:05" happens as a result. The customer with ticket N can go to the clerk (assuming he has not left the building, got into a discussion with his heighbour, gone to the toilet, etc).

Events of one event-type can influence future events of the same type (for example, the clerk can only process one customer at a time, which influences the rate of "customer comes to desk" events) - but each event itself never recurs. The state model is a directed (non-acyclic) graph while the individual events can be considered as forming a poset (ie a DAG) where each event may have been caused by (or for derived events, derived from / inferred from) one or more "preceding" events and may contribute to one or more "succeeding" events.

"Customer C goes to desk D with Number N at 14:05" is a different event from "C goes to D with N at 16:10". These are two distinct events both in the real world and in the model.

Opher Etzion said...

Hi Nigel. Of course they are not the same event when they happen at different times, but they are of the same type. Typically the classification to event hierarchies is done on event types for the sake of static analysis of various types (e.g. optimization).
BTW - the display itself is indeed a state, the event is that the clerk turns on the display written N.



Hans said...

It does seem unrealistic to guarantee a bounded static analysis for every possible set of events and every kind of classification. I think that achieving such a thing would require or imply a breakthrough in algebra.

But there are plenty of "workaround" ideas that capture the cases with a known and tractable solution.