Fast Byzantine Consensus

We present the first protocol that reaches asynchronous Byzantine consensus in two communication steps in the common case. We prove that our protocol is optimal in terms of both number of communication steps and number of processes for two-step consensus. The protocol can be used to build a replicat...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on dependable and secure computing 2006-07, Vol.3 (3), p.202-215
Main Authors: Martin, J.-P., Alvisi, L.
Format: Article
Language:English
Subjects:
Agreements
Byzantine fault tolerance
Communication
Communication system software
Computation
Computer crashes
Computer programming
consensus
Construction
Construction equipment
Delay
Digital signatures
Distributed systems
Failure
Fault tolerance
Fault tolerant systems
Optimization
Pathology
Protocol
Protocols
Safety
Software
Software performance
State machines
Studies
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We present the first protocol that reaches asynchronous Byzantine consensus in two communication steps in the common case. We prove that our protocol is optimal in terms of both number of communication steps and number of processes for two-step consensus. The protocol can be used to build a replicated state machine that requires only three communication steps per request in the common case. Further, we show a parameterized version of the protocol that is safe despite f Byzantine failures and, in the common case, guarantees two-step execution despite some number t of failures (t les f). We show that this parameterized two-step consensus protocol is also optimal in terms of both number of communication steps and number of processes
ISSN:1545-5971
1941-0018
DOI:10.1109/TDSC.2006.35