An Efficient and Fault-Tolerant Solution forDistributed Mutual ExclusionDIVYAKANT AGRAWAL and AMR EL ABBADIUniversity of CaliforniaIn this paper, we present an efficient and fault-tolerant algorithm for generating quorums tosolve the distributed mutual exclusion problem. The algorithm uses a logical tree organization ofthe network to generate tree quorums, which are logarithmic in the size of the network in thebest case. Our approach is resilient to both site and communication failures, even when suchfailures lead to network partitioning. Furthermore, the algorithm exhibits a property of gracefuldegradation, i.e., it requires more messages only as the number of failures increase in thenetwork. We describe how tree quorums can be used for various distributed applications forproviding mutually exclusive access to a distributed resource, managing replicated objects, andatomically committing a distributed transaction.Categories and Subject Descriptors: C .2.4[Computer-Communication Networks]: DistributedSystems; D.4. 1 [Operating Systems]: Process Management– mutual exclusion; D.4.5 [Operat-ing Systems]: Reliability—fault tolerance; D .4.7 [Operating Systems]: Organuatim and De-sign–-distributed systemsGeneral Terms: Algorithms, ReliabilityAdditional Key Words and Phrases: Coteries, logical structures, quorums1. INTRODUCTIONMutual exclusion is crucial for the design of distributed systems. Manyproblems involving replicated data, atomic commitment, distributed sharedmemory, and others require that a resource be allocated to a single process ata time. Solutions to these problems are often vulnerable to site and communi-cation failures. Intersecting quorums can be used to provide fault-tolerantsolutions to mutual exclusion problems. However, they usually incur highcommunication costs. In this paper,we present a new quorum-basedalgorithm which has low communication cost and can handle both types offailures. In particular, this algorithm results in the first distributed mutualThis research was supported by the NSF under grant numbers CCR-8809387 and IRI-8809284and by the University of California and IBM Yorktown Heights under grant numbers MICRO88-179 and 89-137.Authors’ address: Department of Computer Science, University of California, Santa Barbara, CA93106.Permission to copy without fee all or part of this material is granted provided that the copies arenot made or distributed for direct commercial advantage, the ACM copyright notice and the titleof the publication and its date appear, and notice is given that copying is by permission of theAssociation for Computing Machinery. To copy otherwise, or to republish, requires a fee and/orspecific permission.@ 1991 ACM 0734-2071/91/0200-0001 $01.50ACM Transactions on Computer Systems, Vol. 9, No 1, February 1991, Pages 1-20.2.Divyakant Agrawal and Amr El Abbadlexclusion protocol to tolerate both site failures and network partitioningwhile in the best case incurring logarithmic costs in the size of the network.Several algorithms exist to implement mutual exclusion in a distributedenvironment [3, 10, 25, 7, 18, 12, 23, 6, 26, 19, 171. The primary site approach[31 requireslow communication costs but is highly vulnerable to the failure ofthe primary site. Lamport uses logical timestamps [101 to implement dis-tributed mutual exclusion. This protocol prevents starvation at the expenseof requiring a site requesting mutually exclusive access to the resource tocommunicate with all other sites. This makes the protocol fairly expensiveand not resilient to site and communication failures. Schneider [201 proposeda reliable broadcast based approach for synchronization in distributed sys-tems. The broadcast mechanism is used to implement distributed semaphores,which can be employed to achieve mutual exclusion in distributed systems.Reliable broadcasts, however, are expensive and are not generally availablein distributed systems. The majority quorum algorithm [25, 71 is a verysimple and elegant scheme to achieve mutual exclusion in a distributedsystem. In order to attain mutual exclusion, a site must obtain permissionfrom a majority of sites in the network. Since there can be only one majorityat any instant, mutual exclusion is achieved easily. The majority quorumalgorithm is robust and is resilient to both site and communication failures.This algorithm has been particularly used in replicated databases and tosolve the distributed commit problem in systems with site failures andnetwork partitions.In the above protocols, no assumption is made about the logical or physicalorganization of the network. The only assumption required is that any twosites in the network can communicate with each other when there are nofailures. Maekawa [12] proposes implementing distributed mutual exclusionby imposing a logical structure on the network. In this scheme, a set of sitesis associated with each site, and this set has a nonempty intersection with allsets corresponding to the other sites. The rule for constructing these sets isbased on the structure of finite projective planes. A process must obtainpermission from all sites in the set associated with its home site before it canachieve mutual exclusion. Since the set intersects with every other setof other sites, mutual exclusion is guaranteed. The interesting aspect ofMaekawa’s solution is that the size of each of these sets is d, where n is thenumber of sites in the network. Hence, a process needs to communicate withonly v~ sites to obtain permission for mutual exclusion. This is in contrastto the majority quorum algorithm which involves communication with~(n + 1)/2] sites. Thus, imposing a logical structure on thenet,work sig~i~i.cantly reduces the overhead of achieving mutual exclusion.Suzuki and Kasami [23] present a token-based algorithm for distributedmutual exclusion, which requires at most n messages. Helary, Plouzeau, andRaynal [9] propose a token-based algorithm that uses a flooding broadcasttechnique to locate the token. Raymond [17] proposes another token-basedalgorithm that uses a spanning tree of the network for locating the token,ACM ‘hansact,ons on Computer Systems, Vol 9, No 1, February 199JAn Efficient and Fault-Tolerant Solution for Distributed Mutual Exclusion . 3and shows that the average number of messages exchanged in this protocol isO(lolg n). In the best case no communication is necessary since the token maybe available locally while in the worst case the number of messages
View Full Document
Unlocking...