RE: more on preemption

By 'correctness', I mean that the preemption algorithm will never put us in an illegal state configuration.  As far as I can tell, as long as we detect conflicts correctly, then we can use any heuristic we want to resolve conflicts, including flipping a coin, and the algorithm will be 'correct'.   Unless I'm missing something, the issues with preemption heuristics are whether they are clear, or intuitive, or consistent with UML, etc.


-          Jim

From: chris nuernberger [mailto:cnuernber@gmail.com]
Sent: Friday, March 08, 2013 1:27 PM
To: Jim Barnett
Cc: VBWG Public (www-voice@w3.org)
Subject: Re: more on preemption

I don't have time right now.  The error isn't in calculating the exit sets but specifically in deciding how to preempt things.

The error is line:
if isDescendent(t1.source, t2.source):
                    transitionsToRemove.add(t2)
                else:
                    t1Preempted = true
                    break

Where it reads t1.source and t2.source is should be getArena(t1) and getArena(t2).

Chris


On Fri, Mar 8, 2013 at 11:20 AM, Jim Barnett <Jim.Barnett@genesyslab.com<mailto:Jim.Barnett@genesyslab.com>> wrote:
Chris,
Are you saying that we are calculating exit sets incorrectly?  The algorithm detects a conflict between two transitions whenever their exit sets intersect.  There's no mention of source states here (i.e., in the definition of conflict) except insofar as they help determine the exit set. ( Internal transitions are handled in getTransitionDomain(), so their influence on the exit set should also be reflected in the algorithm) Then once a conflict is detected, we look at the source state relationships to determine who preempts whom.   That's our heuristic for resolving conflicts, inherited from UML, but I don't think it effects correctness.  But if we're calculating exit sets incorrectly, that would cause us to be incorrect.

Can you send around an example that shows the problem?

Thanks,
Jim

From: chris nuernberger [mailto:cnuernber@gmail.com<mailto:cnuernber@gmail.com>]
Sent: Friday, March 08, 2013 1:07 PM

To: Jim Barnett
Cc: VBWG Public (www-voice@w3.org<mailto:www-voice@w3.org>)
Subject: Re: more on preemption

I don't think the algorithm is correct.  This goes back to the UML spec which I *also* think is incorrect.

This argument ignores transitions of internal types which is a detail.

The exit set is calculated via the LCCA of the source and the target states.  Let's call this item the transition arena as we have before.

It may be the source but it also may be considerable higher up the state graph than the source.

Your given algorithm only compares the transition sources for descendant qualities when it should compare the transition arenas *because* the sources may be unrelated in the graph *but* the exit sets collide.  A correct algorithm would look *just* like the one given except you would compare the transition arena's for descendent instead of transition sources.

Chris



On Fri, Mar 8, 2013 at 8:12 AM, Jim Barnett <Jim.Barnett@genesyslab.com<mailto:Jim.Barnett@genesyslab.com>> wrote:
There hasn't been any further discussion on this.  Based on the discussion so far, I think that we should say that transitions in descendents preempt transitions in ancestors.)  The UML spec requires this quite clearly (even if the rest of the discussion is confusing) and "descendents preempt ancestors" is one of the basic principles of the language.  Here's a modified preemption algorithm that implements it.

Implementations will be able to do something more efficient.  For example, this algorithm tries to handle the case where a transition t1 conflicts with multiple transitions, say t2 and t3, where t1's source state is a descendent of t2's, but not of t3's.  in this case, t1 is preempted by t3 (because t3 was chosen in a preceding state), so we _keep_ t2, even though it would be preempted by t1 if t1 weren't blocked by t3.  I'm pretty sure that this case can't arise in practice, but I haven't been able to prove it, so I have tried to make the algorithm handle it.

Let me know what you think about both the clarity and correctness of this version.


-          Jim

function removeConflictingTransitions(enabledTransitions)
enabledTransitions will contain multiple transitions only if a parallel state is active. In that case, we may have one transition selected for each of its children. These transitions may conflict with each other in the sense that they have incompatible target states. Loosely speaking, transitions are compatible when each one is contained within a single <state> child of the <parallel> element. Transitions that aren't contained within a single child force the state machine to leave the <parallel> ancestor (even if they reenter it later). Such transitions conflict with each other, and with transitions that remain within a single <state> child, in that they may have targets that cannot be simultaneously active. The test that transitions have non-intersecting exit sets captures this requirement. (If the intersection is null, the transitions are contained in separate <state> descendents of <parallel>. If intersection is non-null, then at least one of the transitions is exiting the <parallel>). When such a conflict occurs, then if the source state of one of the transitions is a descendent of the source state of the other, we select the transition in the descendent. Otherwise we prefer the transition that was selected by the earlier state in document order and discard the other transition. Note that targetless transitions have empty exit sets and thus do not conflict with any other transitions.
We start with a list of enabledTransitions and produce a conflict-free list of filteredTransitions. For each t1 in enabledTransitions, we test it against all t2 that are already selected in filteredTransitions. If there is a conflict, then if t1's source state is a descendent of t2's source state, we prefer t1 and say that it preempts t2 (so we we make a note to remove t2 from filteredTransitions). Otherwise, we prefer t2 since it was selected in an earlier state in document order, so we say that it preempts t1. (There's no need to do anything in this case since t2 is already in filteredTransitions. Furthermore, once one transition preempts t1, there is no need to test t1 against any other transitions.) Finally, if t1 isn't preempted by any transition in filteredTransitions, remove any transitions that it preempts and add it to that list.
function removeConflictingTransitions(enabledTransitions):
    filteredTransitions = new OrderedSet()
// toList sorts the transitions in the order of the states that selected them
    for t1 in enabledTransitions.toList():
        t1Preempted = false;
        transitionsToRemove = new OrderedSet()
        for t2 in filteredTransitions.toList():
            if computeExitSet(t1).hasIntersection(computeExitSet(t2)):
                if isDescendent(t1.source, t2.source):
                    transitionsToRemove.add(t2)
                else:
                    t1Preempted = true
                    break
        if not t1Preempted:
            for t3 in transitionsToRemove.toList():
                filteredTransitions.delete(t3)
            filteredTransitions.add(t1)

    return filteredTransitions




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



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