Efficient solution to the distributed mutual exclusion problem
Divyakant Agrawal, Amr El Abbadi · 1989
We present an efficient fault-tolerant solution to the distributed mutual exclusion problem.Our protocol requires logn messages in the best case and is resilient to both site and communication failures, even when such failures lead to network partitioning.Furthermore, the protocol exhibits a property of graceful degradation, i.e., it requires more message only as the number of failures increase in the network. 1 Int reduction Mutual exclusion is crucial for the design of distributed systems.Many problems involving replicated data, atomic commitment, synchronization in asynchronous systems, and others require that a resource be allocated to a single process at a time.Solutions to this problem often involve high communication costs and are vulnerable to site and communication failures.Several distributed algorithms exist to implement mutual exclusion [l, 5, 16, 4, 11, 7, 15, 3, lo].The primary site approach [l] requires low communica tion costs but is highly vulnerable to the failure of 'This research is supported by the NSF under grant numbers CCR-880938'7 and IRI-8809284 and by the University of California and IBM Yorktown Heights under grant number MICRO 88/179.