Probabilistic language analysis of weighted voting algorithms

ABSTRACT

We present a method of analyzing the performance of weighted voting algorithms in a fault-tolerant distributed system. In many distributed systems, some processors send messages more frequently than others and all processors share a common communication medium, such as an Ethernet. Typical fault-tolerant voting algorithms require that a certain minimum number of votes be collected from different processors. System performance is significantly affected by the time required to collect those votes. We formulate the problem of weighted voting in terms of probabilistic languages and then use the calculus of generating functions to compute the expected delay to collect that number of votes. An application of the method to a particular voting algorithm, the Total protocol, is given.

REFERENCES

• 1: M. Ahamad , M. H. Ammar, Performance Characterization of Quorum-Consensus Algorithms for Replicated Data, IEEE Transactions on Software Engineering, v.15 n.4, p.492-496, April 1989 [doi>10.1109/32.16608]
• 2: D. Barbara , H. Garcia-Molina, The reliability of voting mechanisms, IEEE Transactions on Computers, v.36 n.10, p.1197-1208, Oct. 1987 [doi>10.1109/TC.1987.1676860]
• 3: Boneh, A. and Hofri, M. The coupon collector problem revisited, Technical Report ~549, Department of Computer Science, Technion, Haifa, Israel, Apr. 1989.
• 4: Shun Yan Cheung , Mustaque Ahamad , Mostafa H. Ammar, Optimizing Vote and Quorum Assignments for Reading and Writing Replicated Data, Proceedings of the Fifth International Conference on Data Engineering, p.271-279, February 06-10, 1989
• 5: Feller, W. An introduction to probability theory and its applications, vol. 1, John Wiley & Sons, Inc., New York, 1957.
• 6: Flajolet, P., Curdy, D. and Thimonier, L. Birthday paradox, coupon collectors, caching algorithms and self-organizing search, INRIA RC @720, Aug. 1987.
• 7: 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]
• 8: 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]
• 9: Maurice Herlihy, A quorum-consensus replication method for abstract data types, ACM Transactions on Computer Systems (TOCS), v.4 n.1, p.32-53, Feb. 1986 [doi>10.1145/6306.6308]
• 10: P. M. Melliar-Smith , L. E. Moser , V. Agrawala, Broadcast Protocols for Distributed Systems, IEEE Transactions on Parallel and Distributed Systems, v.1 n.1, p.17-25, January 1990 [doi>10.1109/71.80121]
• 11: Moser, L. E., Melliar-Smith, P. M. and Agrawala, V. Asymptotic broadcast agreement protocols. Submitted for publication.
• 12: 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]
• 13: Tong, Z. and Kain, R. Y. Vote assignments in weighted voting mechanisms, Proceedings of 7th Symposium on Reliable Distributed Systems, Oct. 1988, 138-143.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Reliability, availability, and serviceability

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Protocol verification
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes

General Terms:
Algorithms, Languages, Performance, Reliability