RE: ISSUE-826 Re: More Problems with Preemption

Chris,
There doesn't seem to be any definition of  preemption that everyone finds clear.  I like the one involving transition classes (and it's very efficient, since the classes can be computed at design time), but most other people seem not to.

We don't define 'conflict' for entry sets, so the question would be whether transitions with non-conflicting exit sets can put the state machine in an illegal state configuration.  It would be complex to prove that they cannot, but an informal argument is:  the  only transitions with intersecting exit sets are pairs of class 2 and class 3 transitions or pairs of class3 transitions.  Furthermore, if you're in a legal state set, the only way to get into an illegal one would be to take a class3 transition, plus a class2 or class3 transition, and this definition blocks that.  (This argument assumes that the rest of the algorithm is correct, of course  - you could end up in an illegal configuration if you selected two transitions within a single state, etc., but the algorithm makes sure that doesn't happen.)


-          Jim

From: chris nuernberger [mailto:cnuernber@gmail.com]
Sent: Friday, February 08, 2013 10:14 AM
To: Jim Barnett
Cc: www-voice@w3.org
Subject: Re: ISSUE-826 Re: More Problems with Preemption

OK, I can buy that although I do think it is odd to propose an algorithm that is demonstrably less efficient.  I guess I just find this definition much clearer:

Arena Orthogonal : Two transition occurrences are included in the same small-step only if their arenas are orthogonal, where the arena of a transition is the smallest (lowest in the hierarchy of the composition tree) Or-state that is the (grand)parent of the source and destination control states of the transition.

Obviously that would be the transition arena would be defined by the transition subgraph root.

This is also the definition used in the white paper linked to from SCION's comparison page.

Is it possible that transactions with non-conflicting exit sets would have conflicting entry sets?

Chris

On Fri, Feb 8, 2013 at 8:07 AM, Jim Barnett <Jim.Barnett@genesyslab.com<mailto:Jim.Barnett@genesyslab.com>> wrote:
Speed is not an issue in the algorithm, since implementations are only required to behave _as if_ they are implementing the algorithm in the spec.  There are all sorts of places where the spec algorithm can be optimized (it calculates certain values over and over again, instead of caching them.  And you wouldn't bother with  filterPreempted at all if you only had a single transition.)

I think that the advantage of the version that I proposed is that it is very close to the normative wording of the spec, which is in turn taken from UML, with which we try to stay consistent.


-          Jim

From: chris nuernberger [mailto:cnuernber@gmail.com<mailto:cnuernber@gmail.com>]
Sent: Friday, February 08, 2013 10:02 AM
To: Jim Barnett
Cc: www-voice@w3.org<mailto:www-voice@w3.org>
Subject: Re: ISSUE-826 Re: More Problems with Preemption

In which cases would this algorithm differ from the one I proposed?

The one I proposed is far faster.

Chris



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