Alternators in Read/Write Atomicity

Sandeep S. Kulkarni, Chase Bolen, John Oleszkiewicz and Andrew Robinson


The alternator problem requires that in legitimate states no two neighboring processes are enabled and between two executions of a process, its neighbors execute at least once. In this paper, we present a solution for the alternator problem that has the following properties: (1) If the underlying topology is {\em arbitrary} and the program is executed in read/write atomicity then it is stabilizing fault-tolerant, i.e., starting from an arbitrary state, it recovers to states from where its specification is satisfied, (2) If the underlying topology is {\em bipartite} and the program is executed in the concurrent execution model then it provides stabilizing fault-tolerance and maximal concurrency, (3) If the underlying topology is {\em linear} or {\em tree} then the program provides both these properties, and (4) The program uses bounded state if the network size is known. To our knowledge, this is the first alternator program that achieves these properties.


Return to the publication list
Return to the Sandeep's home page