Efficient Byzantine Fault-Tolerance
Top Cited Papers
- 15 November 2011
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. 62 (1), 16-30
- https://doi.org/10.1109/tc.2011.221
Abstract
We present two asynchronous Byzantine fault-tolerant state machine replication (BFT) algorithms, which improve previous algorithms in terms of several metrics. First, they require only 2f+1 replicas, instead of the usual 3f+1. Second, the trusted service in which this reduction of replicas is based is quite simple, making a verified implementation straightforward (and even feasible using commercial trusted hardware). Third, in nice executions the two algorithms run in the minimum number of communication steps for nonspeculative and speculative algorithms, respectively, four and three steps. Besides the obvious benefits in terms of cost, resilience and management complexity-fewer replicas to tolerate a certain number of faults-our algorithms are simpler than previous ones, being closer to crash fault-tolerant replication algorithms. The performance evaluation shows that, even with the trusted component access overhead, they can have better throughput than Castro and Liskov's PBFT, and better latency in networks with nonnegligible communication delays.Keywords
This publication has 36 references indexed in Scilit:
- Fast Byzantine ConsensusIEEE Transactions on Dependable and Secure Computing, 2006
- Reducing TCB complexity for security-sensitive applicationsACM SIGOPS Operating Systems Review, 2006
- Travelling through wormholesACM SIGACT News, 2006
- Separating agreement from execution for byzantine fault tolerant servicesACM SIGOPS Operating Systems Review, 2003
- COCAACM Transactions on Computer Systems, 2002
- Practical byzantine fault tolerance and proactive recoveryACM Transactions on Computer Systems, 2002
- Minimal Byzantine StorageLecture Notes in Computer Science, 2002
- Implementing fault-tolerant services using the state machine approach: a tutorialACM Computing Surveys, 1990
- Consensus in the presence of partial synchronyJournal of the ACM, 1988
- Reaching Agreement in the Presence of FaultsJournal of the ACM, 1980