VOTING MECHANISMS IN DISTRIBUTED SYSTEMS

This paper illustrates how voting mechanisms can be exploited to improve the reliability of decisions in a distributed system. We assume a model of decision making in which several processors (nodes) are assigned to work independently on various aspects of a problem, and each returns a binary answer to a coordinator node. The coordinator combines the answers using a voting mechanism to arrive at a final answer. Two issues are addressed. If the reliability of each node is known, then by assigning suitable votes to the various nodes, it is possible to maximize the probability of a correct decision by the coordinator. If a cost vs reliability (C-R) function for each node is known, then it is possible to determine a best operating point for each node so as to minimize the total cost of the computation. Algorithms for minimizing the cost were designed and tested, and conditions under which savings can be realized were identified. The magnitude of savings from such a distributed system were a function of the parameters of the individual C-R function. The parameters were associated with the slope (steepness) of the curve, and the savings were larger when the individual curve was steeper. On the other hand, if the slope of the individual curve was below a cut-off, then savings were not realized. The potential for savings from a judicious assignment of votes is illustrated. As one would anticipate, such savings occurred when, and only when, the C-R functions were non-identical.