The vulnerability of vote assignments

ABSTRACT

In a faulty distributed system, voting is commonly used to achieve mutual exclusion among groups of nodes. Each node is assigned a number of votes, and any group with a majority of votes can perform the critical operations. Vote assignments can have a significant impact on system reliability, and in this paper we study the vote assignment problem. To compare vote assignments we define two deterministic measures, node and edge vulnerability. We present various properties of these measures and discuss how they can be computed. For these measures we discuss the selection of the best assignment and propose heuristics to identify good candidate assignments.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 2: Daniel Barbara, Mutual exclusion in distributed systems (databases, voting, partitions), 1985
• 3: BERNE, C. Principles o{ Combinatorics, Academic Press, Orlando, Fla., 1971.
• 4: DAVIDSON, S. Evaluation of an optimistic protocol for partitioned distributed database systems. Tech. Rep. 299, Department of Electrical Engineering and Computer Science, Princeton Univ., Princeton, N.J. 1982.
• 5: DOLL, D. R. Telecommunications turbulance and the computer network evolution. IEEE Computer 7 (Feb. 1974), 13-22.
• 6: FRENCHEN, J. B. Graph connectivity algorithm. In Proceedings of the International Conference in Combinatorial Mathematics, New York Academy of Sciences, Apr., 1970.
• 7: 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]
• 8: GOMOR~, R. E., AND HU, T. C. Multi-Terminal network flows. SIAM J. Appl. Math. 9 (Dec. 1961), 551-570.
• 9: 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]
• 10: GARCIA-MOLINA, H., AND BARBARA, D. Optimizing the reliability provided by voting mechanisms. in Proceedings of the 4th International Conference on Distributed Computing Systems (San Francisco, May), 1984, pp. 340-346.
• 11: HYAFIL, L., AND RIVEST, R. L. Graph partitioning and constructing optimal decision trees are polynomial complete problems. Rep. No. 33, IRIA-Laboria, Rocquencourt, France.
• 12: KLEINROCK, L. Queueing Systems, vol. 2. Wiley, New York, 1976.
• 13: LAMPORT, L. The implementation of reliable distributed multiprocess systems. Comput. Netw. 2 (1978), 95-114.
• 14: Christos H. Papadimitriou , Kenneth Steiglitz, Combinatorial optimization: algorithms and complexity, Prentice-Hall, Inc., Upper Saddle River, NJ, 1982
• 15: SIEWlOREK, D. P., AND SWARZ, R. S. The Theory and Practice of Reliable System Design. Digital Press, Bedford, Mass., 1982.
• 16: 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]
• 17: WHITNEY, H. Congruent graphs and the connectivity of graphs. Amer. J. Math. 54, 150-168.
• 18: WILKOV, R. S. Analysis and design of reliable computer networks. IEEE Trans. Cornmun. 20, 3 (June 1972), 660-678.

INDEX TERMS

Classification:
  B. Hardware
  B.1 CONTROL STRUCTURES AND MICROPROGRAMMING
      B.1.3 Control Structure Reliability, Testing, and Fault-Tolerance**
          Subjects: Error-checking**

  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Distributed applications; Network operating systems
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Reliability, availability, and serviceability

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.5 Reliability
          Subjects: Fault-tolerance

General Terms:
Design, Reliability