--------------------
SCHEDULING ALGORITHM (author:  Jay Misra)
--------------------

An action shares a token with each action with which it is
incompatible.  An action that holds all its shared tokens executes.
Then it gives up all its tokens (to each of its incompatible actions).

Each processor has the following data structure for an action x that
it manages.

N:  number of actions with which x is incompatible,

n:  number of tokens that x does not hold {0 <= n <= N},

Ins:  a set containing pairs of the form (p,y), where p is a processor
id and y is an action with which x is incompatible; y is managed by p.
There should be N such pairs.  It is possible that p is the identity
of the processor itself.

Algorithm for processor i:: {I write n_x for "n of action x"}

 (Forall x managed by i::
   n_x = 0 -> execute x;
              (forall p,y: (p,y) in Ins_x: 
                 if p = i then n_y := n_y - 1 else send token(y) to p
              );
              n := N
 )

[] on receiving token(x) -> n_x := n_x - 1

Initialization:: represent action x at processor p by the pair
(p,x). For each edge in the incompatibility graph, say between (p,x)
and (q,y), assign the corresponding token to the smaller of (p,x) and
(q,y) {each action is assigned a unique ID}.


--------------------------------------
IMPLEMENTATION OF SCHEDULING ALGORITHM
--------------------------------------

Since each item is a thread running on a server, actions that are
compatible with each other may be executed concurrently on the same
server, provided that the actions do not belong to the same item.
Hence when an action is ready to run (i.e., has all the needed tokens)
the scheduler wakes up the action's item and tells it to execute the
action.  When the item discovers (by polling a variable) that it must
execute a particular action, it executes the action and then suspends
itself.

Therefore, the "Forall x" part of Jay's scheduling algorithm is
modified as follows:

 (Forall x managed by i::
   if x finished executing since the last time we looked at x
      then (forall p,y: (p,y) in Ins_x: 
              if p = i then n_y := n_y - 1 else send token(y) to p
           );
           n := N
   else
      if n_x = 0 and x's item is not executing
         then tell x's item to execute x
 )