How to assign votes in a distributed system

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.

REFERENCES

• 1: BENZAKEN, C.Critical hypergraphs for the weak chromatic number. J. Comb. Theory, Series B 29, (1980), 328-338.
• 2: C. Berge, Graphs and Hypergraphs, Elsevier Science Ltd, 1985
• 3: DAVIDSON, S.Evaluation of an optimistic protocol for partitioned distributed database systems. Tech. Rep. 299, Dept. of Electrical Engineering and Comput. Sci., Princeton Univ., May 1982.
• 4: Danny Dolev , H. Raymond Strong, Polynomial algorithms for multiple processor agreement, Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.401-407, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802215]
• 5: GARCIA-MOLINA, H.Reliability issues for fully replicated distributed databases. IEEE Trans. Comput. 15, 9 (Sept. 1982) 34-42.
• 6: David K. Gifford, Weighted voting for replicated data, Proceedings of the seventh ACM symposium on Operating systems principles, p.150-162, December 10-12, 1979, Pacific Grove, California, United States [doi>10.1145/800215.806583]
• 7: LAMPORT, L.The implementation of reliable distributed multiprocess systems. Comput. Networks 2 (1978), 95-114.
• 8: Leslie Lamport , Robert Shostak , Marshall Pease, The Byzantine Generals Problem, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.3, p.382-401, July 1982 [doi>10.1145/357172.357176]
• 9: LOVASZ, L. On chromatic number of finite set systems. Acta Math. Acad. Sci. Hungary 19 (I968), 59-67.
• 10: LOVASZ, L. Coverings and colorings of hypergraphs. In Proceedings of the 4th Southeastern Conference on Combinatorics, Graph Theory and Computing (Florida Atlantic University). Utilitas Mathematica, Winnipeg, Canada, 1973, pp. 3-12.
• 11: LYNCH, N. FISCHER, M., AND FOWLER, R. A simple and efficient byzantine generals algorithm. In Proceedings of the 2nd Symposium on Reliability in Distributed Software and Database Systems (Univ. of Pittsburgh, July). iEEE, New York, i982, pp. 46-52.
• 12: ROTHNIE, J. B., AND GOODMAN, N.A survey of research and development in distributed database management. In Proceedings of the 3rd International Conference on Very Large Database (Tokyo, Japan, Oct. 6-8). ACM, New York, 1977, pp. 48-62.
• 13: SKEEN, D.A quorum-based commit protocol. In Proceedings of the 6th Berkeley Workshop on Distributed Data Management and Computer Networks (Asilomar, Calif., Feb.). Lawrence Berkeley Laboratories, Berkeley, Calif., 1982, pp. 69-80.
• 14: SKEEN, D. Crash recovery in a distributed database system. Ph.D. dissertation, Memorandum UCB/ERL M82/45, Univ. of California at Berkeley, Berkelely, Calif. May 1982.
• 15: Robert H. Thomas, A Majority consensus approach to concurrency control for multiple copy databases, ACM Transactions on Database Systems (TODS), v.4 n.2, p.180-209, June 1979 [doi>10.1145/320071.320076]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Distributed databases

General Terms:
Algorithms, Management, Performance, Theory, Verification