Asynchronous byzantine agreement protocols
type: Item
instance of: scholarly article
title: Asynchronous byzantine agreement protocols
zbMATH Open document ID: 0622.68032
DOI: 10.1016/0890-5401(87)90054-X
author: Gabriel Bracha
published in: Information and Computation
publication date: 1987-01-01T00:00:00Z
review text: A consensus protocol enables a system of n asynchronous processes, some of them faulty, to reach agreement. Both the processes and the message system are capable of cooperating to prevent the correct processes from reaching decision. A protocol is t-resilient if in the presence of up to t faulty processes it reaches agreement with probability 1. Byzantine processes are faulty processes can be deviate arbitrarily from the protocol; Fail-Stop processes can just stop participating in it. In a recent paper, t-resilient randomized consensus protocols were presented for \(t<n/5\). We improve this to \(t<n/3\), thus matching the known lower bound on the number of correct processes necessary for consensus. The protocol uses a general technique in which the behavior of the Byzantine processes is restricted by the use of a broadcast protocol that filters some of the messages. The apparent behavior of the byzantine processes, filtered by the broadcast protocol, is similar to that of fail-stop processes. Plugging the broadcast protocol as a communicating primitive into an agreement protocol for fail-stop processes gives the result. This technique, of using broadcast protocols to reduce the power of the faulty processes and then using them as communication primitives in algorithms designed for weaker failure models, was used successfully in other contexts.
Mathematics Subject Classification ID: 68N25
zbMATH DE Number: 4009808
zbMATH Keywords: consensus protocol
zbMATH Keywords: asynchronous processes
zbMATH Keywords: message system
zbMATH Keywords: Byzantine processes
zbMATH Keywords: broadcast protocol
zbMATH Keywords: fail-stop processes
zbMATH Keywords: communicating primitive
zbMATH Keywords: faulty processes
MaRDI profile type: Publication
cites work: Asynchronous consensus and broadcast protocols
cites work: Impossibility of distributed consensus with one faulty process
cites work: The Byzantine Generals Problem
cites work: Reaching Agreement in the Presence of Faults
description: scientific article; zbMATH DE number 4009808