How to Assign Votes in a Distributed System HECTOR GARCIA-MOLINA AND DANIEL BARBARA Princeton University, Princeton, ,New Jersey Abstract. In a distributed system, one strategy for achieving mutual exclusion of groups of nodes without communication is to assign to each node a number of votes. Only a group with a majority of votes can execute the critical operations, and mutual exclusion is achieved because at any given time there is at most one such group. A second strategy, which appears to be similar to votes, is to define a priori a set of groups that intersect each other. Any group of nodes that finds itself in this set can perform the restricted operations. In this paper, both of these strategies are studied in detail and it is shown that they are not equivalent in general (although they are in some cases). In doing so, a number of other interesting properties are proved. These properties will be of use to a system designer who is selecting a vote assignment or a set of groups for a specific application. Categories and Subject Descriptors: C.2.4 [Computer-Communications Networks]: Distributed Sys- tems--distributed databases; H.2.4 [Database Management]: Systems--distributed systems General Terms: Algorithms, Theory Additional Key Words and Phrases: Distributed databases, mutual exclusion, partitions 1. Introduction In many distributed systems it is necessary to have a mutual exclusion mechanism that works even when nodes fail or the communication lines are broken. For example, consider a system that manages replicated data. Owing to a network partition, the system may be divided into isolated groups of nodes. We probably do not want users at isolated groups updating the database concurrently since this would cause the copies to diverge [ 121. So, if a group is going to perform updates, it must be able to guarantee that no other group is performing this activity. This mutual exclusion has to be enforced without communication between groups. One well-known solution is to assign a priori a number of votes (or points) to each node in the system, and a group whose members have a majority of the total votes is allowed to perform the restricted operation (e.g., [3, 5,6, 151). The mutual exclusion is achieved because at most a single group can have a majority of votes at a time. (It is possible that at a given time no group has a majority and can perform the operation. There seems to be no way to avoid this problem. Even giving one node all votes does not help since that node may fail.) Votes are used to achieve mutual exclusion in a number of other algorithms. For example, in the so-called Byzantine Generals problem, nodes may fail and yield incorrect or even misleading results. The computation being performed must Authors’ present addresses: H. Garcia-Molina, Department of Electrical Engineering and Computer Science, Princeton University, Princeton, NJ 08544; D. Barbara, Universidad Simon Bohvar, Departa- mento de Matematicas y Ciencias de Computation, Sartenejas, Baruta, Venezuela. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the ACM copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Association for Computing Machinery. To copy otherwise, or to republish, requires a fee and/or specific permission. 0 1985 ACM 0004-541 l/85/1000-0841 $00.75 Journal of the Association for Computing Machinery, Vol. 32, No. 4. October 1985, pp. 841-860842 H. GARCIA-MOLINA AND D. BARBARA be replicated, and if nodes with a majority of votes agree on a result, it is considered correct (e.g., [4], [8] and [ 111). Votes are also used in some commit protocols (e.g., [ 131 and [ 141). After a failure, nodes must decide whether to commit or abort a transaction, and the protocol must ensure that at most one group of nodes makes such a decision. A second solution to the mutual exclusion problem was suggested by Lamport in 1978 [7], but because it appears to be so similar to vote assignment, it has received little attention. The idea is to define a priori a set of groups that may perform the restricted operation. Each pair of groups should have a node in common to guarantee mutual exclusion. For example, if we have nodes a, 6, and c we may define the set {{a, b), (b, c), ( a, cl). Nodes a and b can perform the operation together, knowing that neither group (b, c) or {a, c) can be formed. Notice that this set of groups is equivalent to assigning one vote to each node (or n votes to each node). The assignment of votes or the choice of set of groups can have a critical effect on the reliability of a distributed system. Consider, for example, a system with nodes a, b, c, and d and an assignment that gives one vote to each. This seems like a natural choice because it gives each node equal weight. Since three votes are needed for a majority, this is equivalent to the set of groups But now, consider an assignment that gives node a two votes and the rest a single vote. The majority is still three votes, so this is equivalent to R = Ha, 61, Ia, 4 ia, 4, VP c, 41. Set R and its associated vote assignment is clearly superior to S because all groups of nodes that can operate under S can operate under R, but not vice versa. For instance, a and b can form a group under R but not under S. So, if the system splits into groups (a, b ) and (c, d 1, there will be one active group under R but none under S. So clearly, no system designer should ever select set S (or its equivalent vote assignment), in spite of the fact it seems “natural.” We use the term “R dominates S” to mean that R is always superior to S. Obviously, we want to ignore dominated sets (or vote assignments). But even if we do, we must still select one of the nondominated sets, and this is no easy task. In our example, which of the nodes should get the two votes? Or should we give one node one vote and the rest three
View Full Document
Unlocking...