Solving Consensus in a Byzantine Environment Using an Unreliable Fault Detector

Unreliable fault detectors can be used to solve the consensus problem in asynchronous 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 3S(Byz) of eventually strong Byzantine fault detectors and the class 3W(Byz) of eventually weak Byzantine fault detectors and show that any Byzantine fault detector in 3W(Byz) can be transformed into a Byzantine fault detector in 3S(Byz). We present an algorithm that uses a fault detector in 3S(Byz) to solve the consensus problem in an asynchronous distributed system with at most b(n \Gamma 1)=3c Byzantine faults. The class 3W(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. Keywords: Consensus, asynchronous systems, Byzantine fault, unreliable fault (failure) detector, distributed algorithms 1 Introduction Consensus is a funda..