Two General Alternators

Speaker: Dr Furman Haddix

Time: 12:30pm-1:30pm, September 29th, 2006

Location: Nueces Conference Room

Abstract:

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. The limited general 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. 
 
The uniform general alternator is an alternator with uniform processes configured to form a graph of arbitrary topology. Because this alternator has uniform processes, strong fairness and concurrency are properties obtained with a certain probability, due to the possibility of symmetry in states. The size of the state space and the periodicity of critical section execution are dependent upon the initial state. The worst case size of the state space utilized and period between critical sections executions depend upon the diameter of the graph of processes.