F. Furman Haddix and M.G. Gouda (USA)
Alternation, execution semantics, synchronization, self stabilization
An alternator is an array of interacting processes that satisfies three conditions. First, if a process executes its critical section, then no neighbor of that process can execute its critical section at the same state. Second, along any infinite sequence of system states, each process will execute its critical section, an infinite number of times. Third, along any maximally concurrent execution, the alternator will stabilize to a sequence of states in which the processes will execute their critical sections in alternation. A principal reason for interest in alternators is their ability to transform systems correct under serial execution semantics to systems that are correct under concurrent execution semantics. An earlier alternator for arbitrary topology required (2 * dependency graph circumference) states and after stabilization would wait (2 * dependency graph circumference) steps between critical section executions. This alternator requires only 2d+1 states where d is the degree of the graph of process dependencies for the system and after stabilization will require a wait of 2d+1 steps between critical section executions.
Important Links:
Go Back
