The Reliability of Voting Mechanisms
- 1 October 1987
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-36 (10), 1197-1208
- https://doi.org/10.1109/tc.1987.1676860
Abstract
In a faulty distributed system, voting is commonly used to achieve mutual exclusion among groups of isolated 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. In this paper we address the problem of selecting vote assignments in order to maximize the probability that the critical operations can be performed at a given time by some group of nodes. We suggest simple heuristics to assign votes, and show that they give good results in most cases. We also study three particular homogeneous topologies (fully connected, Ethernet, and ring networks), and derive analytical expressions for system reliability. These expressions provide useful insights into the reliability provided by voting mechanisms.Keywords
This publication has 8 references indexed in Scilit:
- How to assign votes in a distributed systemJournal of the ACM, 1985
- The Byzantine Generals ProblemACM Transactions on Programming Languages and Systems, 1982
- Concurrency control in a system for distributed databases (SDD-1)ACM Transactions on Database Systems, 1980
- A Majority consensus approach to concurrency control for multiple copy databasesACM Transactions on Database Systems, 1979
- Concurrency Control and Consistency of Multiple Copies of Data in Distributed IngresIEEE Transactions on Software Engineering, 1979
- Weighted voting for replicated dataPublished by Association for Computing Machinery (ACM) ,1979
- Computing the Reliability of Complex NetworksSIAM Journal on Applied Mathematics, 1977
- Random GraphsThe Annals of Mathematical Statistics, 1959