Efficient Dynamic Voting Algorithms

Abstract

Voting protocols guarantee consistency of replicated data in the presence of any scenario involving non- Byzantine site failures and network positions. While Static Majority Consensus Voting algorithms use static quorums, Dynamic Voting algorithms dynamically adjust quorums to changes in the status of the network of site holding the copies. We propose in this paper two novel dynamic voting algorithms. One, called Optimistic Dynamic Voting, operates on possibly out-of-date information, which greatly increases the efficiency of the algorithm and simplifies its implementation. The other, called Topological Dynamic Voting, explicitly takes into account the topology of the network on which the copies reside to increase the availability of the replicated data. We also compare availabilities of replicated data managed by both algorithms with those of data managed by existing voting protocols using a simulation model with realistic parameters. Optimistic Dynamic Voting is found to perform as well as the best existing voting algorithms while Topological Dynamic Voting performs much better than all other voting algorithms when two or more copies reside in the same non-partitionable group.