CaltechAUTHORS
  A Caltech Library Service

Deterministic voting in distributed systems using error-correcting codes

Xu, Lihao and Bruck, Jehoshua (1998) Deterministic voting in distributed systems using error-correcting codes. IEEE Transactions on Parallel and Distributed Systems, 9 (8). pp. 813-824. ISSN 1045-9219. http://resolver.caltech.edu/CaltechAUTHORS:XULieeetpds98

[img]
Preview
PDF
See Usage Policy.

544Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:XULieeetpds98

Abstract

Distributed voting is an important problem in reliable computing. In an N Modular Redundant (NMR) system, the N computational modules execute identical tasks and they need to periodically vote on their current states. In this paper, we propose a deterministic majority voting algorithm for NMR systems. Our voting algorithm uses error-correcting codes to drastically reduce the average case communication complexity. In particular, we show that the efficiency of our voting algorithm can be improved by choosing the parameters of the error-correcting code to match the probability of the computational faults. For example, consider an NMR system with 31 modules, each with a state of m bits, where each module has an independent computational error probability of 10^-3. In, this NMR system, our algorithm can reduce the average case communication complexity to approximately 1.0825 m compared with the communication complexity of 31 m of the naive algorithm in which every module broadcasts its local result to all other modules. We have also implemented the voting algorithm over a network of workstations. The experimental performance results match well the theoretical predictions.


Item Type:Article
Additional Information:© Copyright 1998 IEEE. Reprinted with permission. Manuscript received 12 Jan. 1998; revised 30 June 1998. This work was supported in part by U.S. National Science Foundation Young Investigator Award CCR-9457811, by the Sloan Research Fellowship, and by DARPA through an agreement with NASA/OSAT.
Subject Keywords:NMR system, communication complexity, majority voting, error-correcting codes, MDS code
Record Number:CaltechAUTHORS:XULieeetpds98
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:XULieeetpds98
Alternative URL:http://dx.doi.org/10.1109/71.706052
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:5483
Collection:CaltechAUTHORS
Deposited By: Archive Administrator
Deposited On:19 Oct 2006
Last Modified:26 Dec 2012 09:13

Repository Staff Only: item control page