Consensus Protocol in Asynchronous Networks with Failures
Abstract
Consensus Protocol in Asynchronous Networks with Failures
Incoming article date: 05.12.2013Consensus problem involves a system of processes, some of which may be faulty. A fundamental problem of fault-tolerant distributed computing is for the reliable processes to reach a agreement on a same decision. One approach to achieving such agreement is for processes to vote and agree on the majority value. In the absence of faults, this works fine, but the vote even one faulty process can swing the outcome. In this paper we present some result of analysis of a mixed-failure model, where t processes may fail, b out of which is the Byzantine failures and remaining c is crash processes. In a asynchronous model of computation for several distributed problems it turns out that a collection of N processes can tolerate c crash failures if 2c < N, while robustness against b Byzantine failures requires 3b < N. Our algorithm rely on a weak definition of the Byzantine failures which disallows them act as a dead or a crash processes and can tolerate the 2(N – 2c)/3 failures.
Keywords: fault tolerance, distributed algorithms, asynchronous networks, byzantine failures