DETERMINISTIC VOTING IN DISTRIBUTED SYSTEMS USING ERROR-CORRECTING CODES

Distributed voting is an important problem in reliable computing. In a n N Modular Redundant(NMR) system, the N computational modules execute identical tasks and they need to periodically vote on their current s tates. In this paper, we propose a deterministic majority voting algor ithm for NMR systems. Our voting algorithm uses error-correcting codes to drastically reduce the average case communication complexity. In p articular, we show that the efficiency of our voting algorithm can be improved by choosing the parameters of the error-correcting code to ma tch the probability of the computational faults. For example, consider an NMR system with 31 modules, each with a slate of m bits, where eac h module has an independent computational error probability of 10(-3). In this NMR system, our algorithm can reduce the average case communi cation complexity to approximately 1.0825m compared with the communica tion complexity of 31m of the naive algorithm in which every module br oadcasts its local result to all other modules. We have also implement ed the voting algorithm over a network of workstations. The experiment al performance results match well the theoretical predictions.