Alternators in read/write atomicity

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 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 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 linear or 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. (C) 2004 Elsevier B.V. All rights reserved.