CaltechAUTHORS
  A Caltech Library Service

Deterministic Voting in Distributed Systems Using Error-Correcting Codes

Xu, Lihao and Bruck, Jehoshua (1996) Deterministic Voting in Distributed Systems Using Error-Correcting Codes. California Institute of Technology . (Unpublished) http://resolver.caltech.edu/CaltechPARADISE:1996.ETR011

[img]
Preview
PDF (Adobe PDF (2.3MB))
See Usage Policy.

2323Kb
[img]
Preview
Postscript
See Usage Policy.

673Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechPARADISE:1996.ETR011

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 to the power of minus 3. In this NMR system, our algorithm can reduce the average case communication complexity to approximately 1.0825m compared with the communication complexity of 31m 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:Report or Paper (Technical Report)
Related URLs:
URLURL TypeDescription
http://www.paradise.caltech.edu/papers/etr011.psPublisherUNSPECIFIED
Group:Parallel and Distributed Systems Group
Record Number:CaltechPARADISE:1996.ETR011
Persistent URL:http://resolver.caltech.edu/CaltechPARADISE:1996.ETR011
Usage Policy:You are granted permission for individual, educational, research and non-commercial reproduction, distribution, display and performance of this work in any format.
ID Code:26063
Collection:CaltechPARADISE
Deposited By: Imported from CaltechPARADISE
Deposited On:04 Sep 2002
Last Modified:26 Dec 2012 13:52

Repository Staff Only: item control page