A distributed mutual exclusion solution derived from real-life examples

ABSTRACT

This paper presents a distributed mutual exclusion solution which is derived from a real-life situation which requires mutual exclusion. The proposed algorithm uses a dynamic information structure and requires between 0 and N message exchanges per critical section invocation, where N is the number of nodes in the network. The algorithm is also proved to be free from deadlock and starvation.

REFERENCES

• Agrawal 1991: Divyakant Agrawal , Amr El Abbadi, An efficient and fault-tolerant solution for distributed mutual exclusion, ACM Transactions on Computer Systems (TOCS), v.9 n.1, p.1-20, Feb. 1991 [doi>10.1145/103727.103728]
• Carvalho 1983: O. S. F. Carvalho, and G. Roucairol: On Mutual Exclusion in Computer Networks, CACM, 26(2), Feb. 1983, 146-147.
• Garcia-Molina 1985: Hector Garcia-Molina , Daniel Barbara, How to assign votes in a distributed system, Journal of the ACM (JACM), v.32 n.4, p.841-860, Oct. 1985 [doi>10.1145/4221.4223]
• Lamport 1978: Leslie Lamport, Time, clocks, and the ordering of events in a distributed system, Communications of the ACM, v.21 n.7, p.558-565, July 1978 [doi>10.1145/359545.359563]
• Maekawa 1985: Mamoru Maekawa, A N algorithm for mutual exclusion in decentralized systems, ACM Transactions on Computer Systems (TOCS), v.3 n.2, p.145-159, May 1985 [doi>10.1145/214438.214445]
• Raymond 1989: Kerry Raymond, A tree-based algorithm for distributed mutual exclusion, ACM Transactions on Computer Systems (TOCS), v.7 n.1, p.61-77, Feb. 1989 [doi>10.1145/58564.59295]
• Ricart 1981: Glenn Ricart , Ashok K. Agrawala, An optimal algorithm for mutual exclusion in computer networks, Communications of the ACM, v.24 n.1, p.9-17, Jan. 1981 [doi>10.1145/358527.358537]
• Ricart 1983: G. Ricart, and A. K. Agrawala: Author's Response, CACM, 26(2), Feb. 1983, 147-148.
• Singhal 1989: Mukesh Singhal, A Heuristically-Aided Algorithm for Mutual Exclusion in Distributed Systems, IEEE Transactions on Computers, v.38 n.5, p.651-662, May 1989 [doi>10.1109/12.24268]
• Suzuki 1985: Ichiro Suzuki , Tadao Kasami, A distributed mutual exclusion algorithm, ACM Transactions on Computer Systems (TOCS), v.3 n.4, p.344-349, Nov. 1985 [doi>10.1145/6110.214406]
• van de Snepscheut 1987: J. L. A. van de Snepscheut: Fair Mutual Exclusion on a Graph of Processes, Distributed Computing, 2, 1987, 113-115.

INDEX TERMS

Keywords:
critical section, deadlock, distributed system, information structure, mutual exclusion, starvation, sychronization