×

You are using an outdated browser Internet Explorer. It does not support some functions of the site.

Recommend that you install one of the following browsers: Firefox, Opera or Chrome.

Contacts:

+7 961 270-60-01
ivdon3@bk.ru

Consensus Protocol in Asynchronous Networks with Failures

Abstract

Consensus Protocol in Asynchronous Networks with Failures

M.O. Krivosheyev, Y.N. Logvinov

Incoming article date: 05.12.2013

Consensus 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