Vote assignments in weighted voting mechanisms

Abstract

It is shown that voting can provide the maximum reliability if all nodes have reliability p>or=0.5. Thus, a system designer only needs to consider vote assignments in implementing mutual exclusion mechanisms. Some effective vote assignment algorithms are proposed. Neglecting link failures, it is found that the voting weight for each node can be determined by computing a logarithmic function of local information. Voting operations are formally defined, and an optimization objection function is formulated. A sufficient condition for optimal vote assignment and optimal sets of groups is presented, and it is shown that predefining a set of groups to achieve mutual exclusion is not feasible for a large system. Some algorithms generating optimal or suboptimal assignments for systems with perfect links are proposed. Some variations for systems with imperfect links are discussed, along with some comparisons of the new algorithms against previous algorithms proposed for the problem.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>