The Computer Journal Advance Access originally published online on January 26, 2007
The Computer Journal 2007 50(3):341-347; doi:10.1093/comjnl/bxl085
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||
State-Optimal Alternator for Uniform Synchronous Rings1
Department of Information Engineering and Computer Science, Feng Chia University, Taichung 407, Taiwan, ROC
* Corresponding author: E-mail: tjliu{at}fcu.edu.tw
Received 17 May 2006; revised 6 December 2006
An alternator is a network of concurrent nodes, which satisfies the following conditions: (i) if one node enters its critical section, no neighboring nodes could enter their critical sections at the same computing phase; (ii) along any infinite computing phases, each node enters its critical section infinitely often. An alternator is said to exhibit strong fairness if condition (ii) is changed to: between any two consecutive critical steps of a node, all neighbors enter their critical sections exactly once. In this paper, we propose a state-optimal alternator algorithm for uniform rings with n nodes, where n is any positive integer greater than one. The proposed algorithm operates correctly for synchronous mode. Every node maintains only a two-state variable. The proposed algorithm has the snap property that the system always satisfies condition (i) of the alternator even if some transient fault occurs. The stabilization time of the proposed alternator algorithm is O(n) phases. After stabilization, the system satisfies the strong fairness property and achieves the maximal performance. We say that an alternator achieves the maximal performance if a node is allowed to enter its critical section when both its neighbors do not enter their critical sections. In the worst case, the proposed algorithm allows each node to enter its critical section every three phases.
Key Words: Alternator • distributed system • fault-tolerance • self-stabilization • synchronization