Analysis of the Behavior and Reliability of Voting Systems Comprising

Yacoub, Sherif

HP Development Company

关键词: voting;    reliability analysis;    decision making;   

RP-ID  :  HPL-2002-117

学科分类：计算机科学（综合）

美国|英语

来源: HP Labs

【 摘 要 】

Voting is a commonly used technique in combining results from peer experts. In distributed decision making systems, voting mechanisms are used to obtain a decision by incorporating the opinion of multiple units. Voting systems has many applications in fault tolerant systems, mutual exclusion in distributed systems, and replicated databases. We are specifically interested in voting systems as used in decision- making applications. The voting system studied in this paper consists of N units, each has three states: correct (success), wrong (failed), and abstain (did not produce an output). The final output of the decision-making (voting) system is correct if a consensus is reached on a correct unit output, abstain if all units abstain from voting, and wrong otherwise. In this paper, we describe a synthetic experimental procedure to study the behavior of voting systems using a simulator that we developed to: analyze the state of each expert, apply a voting mechanism, and analyze the voting results. For this analysis, we study the following behaviors of a voting system: 1) the reliability of the voting system, "R"; 2) the probability of reaching a consensus, "Pc"; 3) certainly index, "T"; and 4) the confidence index, "C". The configuration parameters controlling the analysis are: 1) the number of participating experts, "N", 2) the possible output states of an expert, and 3) the probability distribution of each expert states. Results of this study unleash several behaviors of a decision-making system with tri-state experts as function of various configuration parameters. 22 Pages