Capacity of voting systems

Data replication is often used to increase the availability of data in a database system. Voting schemes can be used to manage this replicated data. The authors use a simple model to study the capacity of systems using voting schemes for data management. Capacity of a system is defined as the number of operations the system can perform successfully, on an average, per unit time. The capacity of a system using voting is examined and compared with the capacity of a system using a single node. It is shown that the maximum increase in capacity by the use of majority voting is bounded by 1/p, where p is the steady-state probability of a node being alive. It is also shown that for a system employing majority voting, if the reliability of nodes is high, increasing the number of nodes to more than three gives only a marginal increase in capacity. Similar analyses are performed for three other voting schemes