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 n

completes, then any request that completes with a
higher sequence number n� ≥ n has a history h that
n�
includes h as a prefix.
n

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 completes.

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 synchrony⁷ can be achieved by using exponentially increasing timeouts. ⁴

table 1: Labels given to fields in messages.

Label
c
CC
d

i, j h n

m
max
n
n
ND

o OR POM r t u

meaning

Client ID

Commit certificate

Digest (cryptographic one-way hash) of client request message:

d = H(m)

Server IDs

History through sequence number h encoded as cryptographic
n
one-way hash: h = H(h , d)
n n− 1

message containing client request maximum sequence number accepted by replica

Sequence number

Selection of nondeterministic values needed to execute a request 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 view number

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 s_c

replica it believes to be the primary (i.e., the primary for the last response the client received).