Title :
A real-time algorithm for fair interprocess synchronization
Author :
Tsay, Yih-Kuen ; Bagrodia, Rajive L.
Author_Institution :
Dept. of Comput. Sci., California Univ., Los Angeles, CA, USA
Abstract :
The implementation of nondeterministic pairwise synchronous communication among a set of asynchronous processes is modeled as a binary interaction problem. An algorithm for this problem, which satisfies a strong fairness property that guarantees freedom from process starvation, is described. The message and time complexities are independent of the total number of processes in the system. The ways in which the algorithm may be extended to cope with fail-stop process failures are discussed
Keywords :
communication complexity; computational complexity; synchronisation; asynchronous processes; binary interaction problem; fail-stop process failures; fair interprocess synchronization; message complexity; nondeterministic pairwise synchronous communication; real-time algorithm; strong fairness property; time complexities; Abstracts; Algorithm design and analysis; Computational modeling; Computer languages; Computer science; Fault tolerance; Fault tolerant systems;
Conference_Titel :
Distributed Computing Systems, 1992., Proceedings of the 12th International Conference on
Conference_Location :
Yokohama
Print_ISBN :
0-8186-2865-0
DOI :
10.1109/ICDCS.1992.235117
