TokenRingThreeBit.prot

// Three bit token ring defined in
// Title: The Stabilizing Token Ring in Three Bits
// Author: Mohamed G. Gouda and F. Furman Haddix
// Year: 1996

constant N := 3;

direct variable t[N] < 2;
puppet variable e[N] < 2;
puppet variable ready[N] < 2;

// Make the invariant exactly this, no smoothing over puppet variables is allowed.
(future & shadow)
(
  // One process has the token.
  (unique i < N :
      i == 0 && t[i-1] == t[i]
   || i != 0 && t[i-1] != t[i]
  )
  //&&
  //// Some process is enabled.
  //// This and the actual token-passing behavior are
  //// already enforced by the shadow protocol.
  //// already enforced by the shadow protocol.
  //(exists i < N :
  //    i == 0 && e[i-1] == e[i]
  // || i != 0 && e[i-1] != e[i]
  //)
);

process Bot[i < 1]
{
  read:  e[i-1], t[i-1];
  write: e[i], t[i], ready[i];

  // Enforce this behavior within the invariant:
  shadow action:( t[i-1] == t[i] --> t[i] := 1 - t[i-1]; );

  // Use these actions:
  puppet action:
    ( e[i-1] == e[i] && t[i-1] != t[i]
      --> e[i] := 1-e[i-1]; ready[i] := 0;
    );
  puppet action:
    ( e[i-1] == e[i] && t[i-1] == t[i] && !(t[i] == 1 || ready[i] == 1)
      --> e[i] := 1-e[i-1]; ready[i] := 1;
    );
  puppet action:
    ( e[i-1] == e[i] && t[i-1] == t[i] &&  (t[i] == 1 || ready[i] == 1)
      --> e[i] := 1-e[i-1]; t[i] := 1-t[i-1]; ready[i] := 0;
    );
}

process P[i <- map tid < N-1 : tid+1]
{
  read:  e[i-1], t[i-1];
  write: e[i], t[i], ready[i];

  // Enforce this behavior within the invariant:
  shadow action:( t[i-1] != t[i] --> t[i] := t[i-1]; );

  // Use these actions:
  puppet action:
    ( e[i-1] != e[i] && t[i-1] == t[i]
      --> e[i] := e[i-1]; ready[i] := 0;
    );
  puppet action:
    ( e[i-1] != e[i] && t[i-1] != t[i] && !(t[i] == 1 || ready[i] == 1)
      --> e[i] := e[i-1]; ready[i] := 1;
    );
  puppet action:
    ( e[i-1] != e[i] && t[i-1] != t[i] &&  (t[i] == 1 || ready[i] == 1)
      --> e[i] := e[i-1]; t[i] := t[i-1]; ready[i] := 0;
    );
}