Separating agreement from execution for byzantine fault tolerant services
- 19 October 2003
- journal article
- Published by Association for Computing Machinery (ACM) in ACM SIGOPS Operating Systems Review
- Vol. 37 (5), 253-267
- https://doi.org/10.1145/1165389.945470
Abstract
We describe a new architecture for Byzantine fault tolerant state machine replication that separates agreement that orders requests from execution that processes requests. This separation yields two fundamental and practically significant advantages over previous architectures. First, it reduces replication costs because the new architecture can tolerate faults in up to half of the state machine replicas that execute requests. Previous systems can tolerate faults in at most a third of the combined agreement/state machine replicas. Second, separating agreement from execution allows a general privacy firewall architecture to protect confidentiality through replication. In contrast, replication in previous systems hurts confidentiality because exploiting the weakest replica can be sufficient to compromise the system. We have constructed a prototype and evaluated it running both microbenchmarks and an NFS server. Overall, we find that the architecture adds modest latencies to unreplicated systems and that its performance is competitive with existing Byzantine fault tolerant systems.Keywords
This publication has 31 references indexed in Scilit:
- COCAACM Transactions on Computer Systems, 2002
- The timed asynchronous distributed system modelIEEE Transactions on Parallel and Distributed Systems, 1999
- Byzantine quorum systemsDistributed Computing, 1998
- The part-time parliamentACM Transactions on Computer Systems, 1998
- A general theory of composition for a class of "possibilistic" propertiesIEEE Transactions on Software Engineering, 1996
- Implementing fault-tolerant services using the state machine approach: a tutorialACM Computing Surveys, 1990
- Data diversity: an approach to software fault toleranceIEEE Transactions on Computers, 1988
- Scale and performance in a distributed file systemACM Transactions on Computer Systems, 1988
- Asynchronous consensus and broadcast protocolsJournal of the ACM, 1985
- A method for obtaining digital signatures and public-key cryptosystemsCommunications of the ACM, 1978