execute the request and send their responses to the client.
A request completes at a client when the client has a sufficient number of matching responses to ensure that all correct replicas will eventually execute the request and all preceding requests in the same order, thus guaranteeing that all
correct replicas process the request in the same way, issue
the same reply, and transition to the same subsequent system state. To allow a client to determine when a request
completes, a client receives from replicas responses that include
both an application-level reply and the history on which the
reply depends. The history is the sequence of all requests executed by a replica prior to and including this request.
As Figure 1 illustrates, a request completes at a client in
one of two ways. First, if the client receives 3f + 1 matching
responses (Figure 1a), then the client considers the request
complete and acts on it. Second, if the client receives between
2f + 1 and 3f matching responses (Figure 1b), then the client
gathers 2f + 1 matching responses and distributes this
commit certificate to the replicas. A commit certificate includes
cryptographic proof that 2f + 1 servers agree on a linearizable order for the request and all preceding requests, and
successfully storing a commit certificate to 2f + 1 servers
(and thus at least f + 1 correct servers) ensures that no other
ordering can muster a quorum of 2f + 1 servers to contradict
this order. Therefore, once 2f + 1 replicas acknowledge receiving a commit certificate, the client considers the request
complete and acts on the corresponding reply.
Zyzzyva then ensures the following safety condition:
saf If a request with sequence number n and history h
completes, then any request that completes with a
higher sequence number n� ≥ n has a history h that
includes h as a prefix.
If fewer than 2f + 1 responses match, then to ensure liveness the client retransmits the request to all replicas at increasing intervals, and replicas demand that the primary orders retransmitted requests. If the primary orders requests
too slowly or orders requests inconsistently, a replica will
suspect that the primary is faulty. If a sufficient number of
replicas suspect that the primary is faulty, then a view change
occurs and a new primary is elected.
Zyzzyva thereby ensures the following liveness condition
assuming eventual synchrony§:
liv Any request issued by a correct client eventually
In the rest of this section, we detail Zyzzyva’s agreement
subprotocol by considering three cases: ( 1) the fast case when
all nodes act correctly and no timeouts occur, ( 2) the
two-phase case that can occur when a nonprimary replica is faulty
or some timeouts occur, and ( 3) the view change case that can
occur when the primary is faulty or more serious timeouts
occur. Table 1 summarizes the labels we give to fields in messages. Most readers will be happier if on their first reading
they skip the text marked “Additional Pedantic Details.”
§ In practice, eventual synchrony7 can be achieved by using exponentially increasing timeouts. 4
table 1: Labels given to fields in messages.
Digest (cryptographic one-way hash) of client request message:
d = H(m)
History through sequence number h encoded as cryptographic
one-way hash: h = H(h , d)
n n− 1
message containing client request
maximum sequence number accepted by replica
Selection of nondeterministic values needed to execute a
operation requested by client
order request message
Proof of misbehavior
Application reply to a client operation
Time stamp assigned to an operation by a client
3. 1. fast case
Figure 1a illustrates the basic flow of messages in the fast
case. We trace these messages through the system to explain
the protocol, with the numbers in the figure corresponding
to the numbers of major steps in the text. As the figure illustrates, the fast case proceeds in four major steps:
1. Client sends request to the primary.
2. Primary receives request, assigns sequence
number, and forward ordered request to replicas.
3. Replica receives ordered request, speculatively
executes it, and responds to the client.
4a. Client receives 3f + 1 matching responses and
completes the request.
To ensure correctness, the messages are carefully constructed to carry sufficient information to link these steps
with one another and with past system actions. We now
detail the contents of each message and describe the steps
each node takes to process each message.
3. 1. 1. Message processing details
1. Client sends request to the primary.
A client c requests an operation o be performed by the replicated service by sending a message 〈request, o, t, c〉 to the
replica it believes to be the primary (i.e., the primary for the
last response the client received).