Solving Consensus in a Byzantine Environment Using an Unreliable Fault Detector.

Abstract

Unreliable fault detectors can be used to solve the consensus problem in asyn-chronous distributed systems that are subject to crash faults. We extend this result to asynchronous distributed systems that are subject to Byzantine faults. We define the class (Byz) of eventually strong Byzantine fault detectors and the class (Byz) of eventually weak Byzantine fault detectors and show that any Byzantine fault detector in (Byz) can be transformed into a Byzantine fault detector in (Byz). We present an algorithm that uses a fault detector in (Byz) to solve the consensus problem in an asynchronous distributed system with at most \t Byzantine faults. The class (Byz) of Byzantine fault detectors is the weakest class of fault detectors that can be used to solve consensus in such an asynchronous distributed system.