Re: ISSUE-826 Re: More Problems with Preemption

Jim,

What precisely about nonconflicting arenas isn't clear?  It is a *lot* more
clear than the type system given in the specification.

Given a clear definition of arena you could refactor EnterStates,
ExitStates and IsPreempted to all use transition arena.  The pseudocode
would be easier to understand, more factored, and easier to prove correct
if the definition of a transitions enter-set and exit-set were based off of
arena.

An implicit assumption I have is that we have to preempt transitions from
states that would be exited.  I think this would happen automatically due
to the transition selection process but without proving it I think the
preemption algorithm should take that into effect.  I can see, however,
that it perhaps doesn't need to happen because code in that transition
could be protected with an 'In' query.

The problem with classes or types is that they don't take the graph of
*both* transitions into account.  So either you get transitions in
logically distinct regions of the state graph that are unnecessarily
preempted *or* you get invalid transitions like we see in the example.  You
can't come up with a definition of transition class that will avoid this
problem because it doesn't take the *other* transition's local position in
the state graph into account.

Subgraph roots or arenas is *more*  efficient than set comparison and is
what is used in other more proven state machine systems (see paper below).

Pretty much it boils down to this:

1.  Types or categories are either too permissive or too restrictive
because they don't take the combined graph defined by both transitions into
account.

2.  If you are going to go with arenas, then my definition is easier to
understand and prove correct because it isn't immediately obvious that the
transition's entry set will be protected in your algorithm.

The set algorithm you proposed is slower and doesn't take targetless
transitions nor the entry set into account.  It's only benefit compared to
what I proposed is that it is 'like UML' as far as I can see.

The isDescendant function can be computed in O(1) given nodes that are
numbered in a depth first traversal.  The transition arena can be
precomputed, identically as a type or class.  Thus, really, the algorithm I
proposed is O(1) given some simple precomputation on the state graph.


Do you have a solid, technical reason why the specification shouldn't be
change to include the definition of arena along with the algorithm that I
proposed?  I don't agree that going with inferior algorithms in order to be
'like' something else is a solid technical reason.  I *know* (can prove)
that any solution based on types or classes will not be as correct and it
is sure harder to see what its implications are from reading it.

Given a choice, I certainly would pick set comparison over any sort of type
or class comparison but we should look for the 'best' option and since
people are implementing their machines by directly translating the
pseudo-code, why not put the best algorithm in the code as possible?
 Furthermore it allows the introduction of a new, clear, and unambiguously
defined concept (arenas).  This concept allows the pseudocode to be
refactored to be clearer in three places (enterSet, exitSet, isPreempted).

https://cs.uwaterloo.ca/~nday/Papers/uw-scs-tr-2009-05.pdf

Chris



On Fri, Feb 8, 2013 at 8:39 AM, Jim Barnett <Jim.Barnett@genesyslab.com>wrote:

>  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>
> 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]
> *Sent:* Friday, February 08, 2013 10:02 AM
> *To:* Jim Barnett
> *Cc:* 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 ****
>



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