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

overheads.

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

services.

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 permissions@acm.org. The definitive version of this paper can be found at ACM’s Digital Library --http://www.acm.org/dl/.

Details