RE: revisiting preemption

There is a problem with the definition of preemption based on a the transition's source state being in a previous transition's exit set.  Consider a high-level state  S containing a  transition T triggered by event E, and suppose that this transition takes you to some remote state S_far of the state machine.  Now suppose nested deeply inside S is a parallel state with children p1, p2, p3.  How suppose p1 has a transition targeted at p2, but that neither p3 nor any descendent state of S has a  transition defined for E.  p3 will inherit transition T from S.  T will _not_ be preempted, because the transition between p1 and p2 doesn't' cause S to be exited (the parallel state is nested several levels down inside S).  Using this definition of preemption, we end up in p1, p2, p3 _and S_far, which is an illegal configuration.

The definition based on exit sets doesn't have this problem,  since p1, p2, p3 _are_ in transition T's exit set.  The definition based on source state doesn't work right for transitions that are inherited from ancestors.  (If you change the definition to act as if T was copied down into p3, or to say "if the state that selected the transition is in the exit set of a previous transition" , you end up with a definition that's equivalent to the one based on intersecting exit sets.)


-          Jim

From: chris nuernberger [mailto:cnuernber@gmail.com]
Sent: Monday, February 18, 2013 12:02 PM
To: Jim Barnett
Cc: www-voice@w3.org
Subject: Re: revisiting preemption

1.  I would of course like another definition.

2.  My feeling is to preempt transitions if their source state is in the exit set of another transition regardless of it they are targetless or not.  The reason is because it leaves the algorithm open to not even consider transitions from atoms in the configuration that are in a previous transition's exit set.  This could be a significant speed increase in some situations because you can trim the atom list as you process transitions.  Walking up from the atom to the root to find a transition (and run the conditions and such) sometimes does take time, so a short circuit as powerful as not having to consider the atom at all is a big win IMO.

3.  I would vote for as modular and functionally decomposed pseudo-code as possible as it is easier to translate into functional code.

Chris

On Mon, Feb 18, 2013 at 7:58 AM, Jim Barnett <Jim.Barnett@genesyslab.com<mailto:Jim.Barnett@genesyslab.com>> wrote:
There seems to be agreement that the existing definition of preemption is vague and confusing.   It can be made precise, but that still may leave it confusing.  This leaves us with three questions:


1.       Do we want another definition of preemption?  The obvious candidate is UML's definition:  two transitions conflict if their exit sets have a non-null intersection. We can tweak the definition based on transition classes/types to have the same semantics, so the real question is:  which definition is easier to understand?

2.       What do we want to do about targetless transitions?  They have an empty exit set, so on the UML definition they don't preempt any transitions and don't preempt any other transitions.  The existing definition (based on transition types/classes) says (in effect) that a targetless transition is preempted by any preceding transition that exits its source state.  This may seem intuitively clear, but it isn't necessary by any means.  The whole point of preemption is to block transition sets that could produce an illegal configuration, and targetless transitions will never do that.   By not preempting targetless transitions, we end up with the largest set of transitions that can be guaranteed not to cause problems.

3.       When we discussed this issue in the past, we decided that preemption is so complicated that it should be defined in a separate place, hence we have 'filterPreempted' as a separate function.  On the other hand, the filtering could be folded  back into the selectTransitions functions, particularly if it is based on the intersection of exitSets.   So we could consider getting rid of filterPreempted as a separate function.  However, if we do this, we have to insert the same conflict/preemption-detecting logic in both selectEventlessTransitions and selectTransitions, so it may be better to keep it factored out into a  separate function.


-          Jim




--
A foolish consistency is the hobgoblin of little minds - Emerson