Toggle Main Menu Toggle Search

Open Access padlockePrints

With Less Malicious Byzantine Generals: Agreement Algorithms Under Value Faults

Lookup NU author(s): Dr Paul Ezhilchelvan

Downloads


Abstract

Reaching agreement in the presence of faults is a fundamental problem in fault tolerant distributed computing. This paper describes, and establishes the correctness of algorithms for reaching distributed agreement in the presence of faults which are less "malicious" than Byzantine faluts. Consistent value faults and value faults are the two types of faults considered. Faults of these two types cause a processor to fail by producing incorrect output values. Assumptions have been made to exclude a faulty processor's "malicious" failure modes such as a faulty processor's ability to "impersonate" another faulty processor. However, it is considered to be possible for a processor to fail, due to "accidental" sources of errors, by "two-facing", i.e., by delivering one value to one processor and a different or no value to another processor. Taking an upper bound on the number of processors that can possibly fail, an agreement algorithum is developed for each type of fault. It has been shown that these algorithms are optimal with respect to time complexity. The development of these agreement algorithms illustrates that reaching agreement does not turn out to be a simple task, despite the exclusion of malicious failure modes of fault processors.


Publication metadata

Author(s): Ezhilchelvan PD

Publication type: Report

Publication status: Published

Series Title: Computing Laboratory Technical Report Series

Year: 1988

Pages: 17

Print publication date: 01/01/1988

Source Publication Date: January 1988

Report Number: 252

Institution: Computing Laboratory, University of Newcastle upon Tyne

Place Published: Newcastle upon Tyne

URL: http://www.cs.ncl.ac.uk/publications/trs/papers/252.pdf


Share