Voting using predispositions

We present a new, more comprehensive probabilistic model for the voting problem. This model incorporates four distinct probability distributions which can represent the behavior of faulty and nonfaulty modules as well as any underlying probability distribution on the space of answers. Most previous work ignored one or more of these distributions or made implicit or explicit simplifying assumptions about them. Using the new model as a foundation, we present novel voting algorithms which are superior to previous algorithms and which are provably optimal. Our optimal voting algorithms are considerably more complex than most earlier voting schemes. Indeed, the most complex calculation of previous schemes was often a weighted sum. We believe that this simplicity of computation was in part due to hardware limitations which are not as relevant today. Microprocessors can be programmed with our algorithms and can provide a continuously updated stream of answers which are usable in applications which allow sufficient latency between voting times. These optimal algorithms are also relevant in the many applications of voting in distributed systems including Byzantine agreement and clock synchronization. In distributed systems, each node contains its own voter which is typically implemented in software, making it well-suited for our optimal algorithms. Some applications still require simpler voting algorithms; hence we compare several preexisting, commonly implemented voting algorithms. This comparison reveals the desirable characteristics of the plurality voting scheme