Title :
Fault-tolerant algorithms for fair interprocess synchronization
Author :
Tsay, Yih-Kuen ; Bagrodia, Rajive L.
Author_Institution :
Dept. of Comput. Sci., California Univ., Los Angeles, CA, USA
fDate :
7/1/1994 12:00:00 AM
Abstract :
The implementation of nondeterministic pairwise synchronous communication among a set of asynchronous processes is modeled as the binary interaction problem. The paper describes an algorithm for this problem that satisfies a strong fairness property that guarantees freedom from process starvation. This is the first algorithm for binary interactions with strong fairness whose message cost and response time are independent of the total number of processes in the system. The paper also describes how the fair algorithm may be extended to tolerate detectable fail-stop failures. Finally, we show how any solution to the dining philosophers problem can be embedded to design a fair algorithm for binary interactions. In particular, this embedding is used to derive a fair algorithm that can cope with undetectable fail-stop failures.<>
Keywords :
concurrency control; distributed algorithms; fault tolerant computing; synchronisation; asynchronous processes; binary interaction problem; binary interactions; dining philosophers problem; embedding; fair interprocess synchronization; fault-tolerant algorithms; message cost; response time; strong fairness property; Algorithm design and analysis; Computer languages; Computer science; Costs; Delay; Distributed algorithms; Fault tolerance; Postal services;
Journal_Title :
Parallel and Distributed Systems, IEEE Transactions on