Ramakrishna Kotla, Lorenzo Alvisi, Mike Dahlin, Allen Clement, and Edmund Wong
A longstanding vision in distributed systems is to build reliable systems from unreliable components.
An enticing formulation of this vision is Byzantine Fault-Tolerant (BFT) state machine
replication, in which a group of servers collectively act as a correct server even if some of the servers
misbehave or malfunction in arbitrary (“Byzantine”) ways. Despite this promise, practitioners hesitate
to deploy BFT systems, at least partly because of the perception that BFT must impose high
In this article, we present Zyzzyva, a protocol that uses speculation to reduce the cost of BFT
replication. In Zyzzyva, replicas reply to a client’s request without first running an expensive threephase
commit protocol to agree on the order to process requests. Instead, they optimistically adopt
the order proposed by a primary server, process the request, and reply immediately to the client.
If the primary is faulty, replicas can become temporarily inconsistent with one another, but clients
detect inconsistencies, help correct replicas converge on a single total ordering of requests, and
only rely on responses that are consistent with this total order. This approach allows Zyzzyva to
reduce replication overheads to near their theoretical minima and to achieve throughputs of tens of
thousands of requests per second, making BFT replication practical for a broad range of demanding
In ACM Transactions on Computer Systems (TOCS)
Publisher Association for Computing Machinery, Inc.
Copyright © 2007 by the Association for Computing Machinery, Inc. Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from Publications Dept, ACM Inc., fax +1 (212) 869-0481, or email@example.com. The definitive version of this paper can be found at ACM’s Digital Library --http://www.acm.org/dl/.