Comparative Performance Evaluation of Three Voting Schemes

摘要

In this paper, three algorithms for fault-tolerance in multiprocessor and multicomputer systems have been evaluated and compared. All three algorithms rely on the retriability of a computation task. Two of these algorithms (TMR and DMR) are iterative in nature and the outcome at each retry is independent of the previous trials. The third one (RAFT) is a recursive algorithm, at every retry the result is compared to all the previous ones for that task. The schemes were evaluated according to three types of measures: (l)the system reliability as expressed by the quality of the decision and the quality of the decision improvement factor, (2) the overhead incurred in both number of retries and total number of processors used and (3) the relative improvement per unit of overhead. From the performance evaluation of these three schemes we can conclude that, in the general case, TMR provides good relability. In particular when the reliability of the single processor (p) can be arbitralily low, the TMR algorithm provides a better performance than the other two schemes. When the reliability of a single processor can be expected to be larger than 0.7 then the RAFT and DMR algorithms provide a better reliability than TMR with a lower cost in overhead. Furthermore, it was observed that for these values of p the RAFT and DMR algorithms have the exact same performance levels.