A Uniform General Alternator

F. Haddix and W. Peng (USA)


Operating systems support, process synchronization, self stabilization


We introduce an alternator with uniform processes configured to form a graph of arbitrary topology. Some important properties of alternators, in general, are that they are free from deadlock, protect against simultaneous execution of the critical sections of dependent processes, and after a finite number of executions provides a high degree of concurrency and some degree of fairness (deterministically or stochastically). 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. An important value of alternators is their capacity for transforming systems correct under serial (interleaving) semantics to systems correct under concurrent or maximal (power set) semantics. This is based upon a graph of processes representing the alternator in which the vertices are processes and the arcs are dependencies between processes.

Important Links:

Go Back