expires before the client receives 2f + 1 local-commit messages then the client moves on to protocol steps described in
the next subsection.
3. 2. 2. Client trust
At first glance, it may appear imprudent to rely on clients to
transmit commit certificates to replicas (4b): what if a faulty
client sends an altered commit certificate (threatening safety)
or fails to send a commit certificate (imperiling liveness)?
Safety is ensured even if clients are faulty because commit certificates are authenticated by 2f + 1 replicas. If
a client alters a commit certificate, correct replicas will
ignore it.
Liveness is ensured for correct clients because commit certificates are cumulative: successfully storing a commit certificate for request n at 2f + 1 replicas commits those replicas
to a linearizable total order for all requests up to request n.
So, if a faulty client fails to deposit a commit certificate, that
client may not learn when its request completes, and a replica whose state has diverged from its peers may not immediately discover this fact. However, if at any future time a correct client issues a request, that request (and a linearizable
history of earlier requests on which it depends) will either
( 1) complete via 3f + 1 matching responses (4a), ( 2) complete
via successfully storing a commit certificate at 2f + 1 replicas
(4b– 6), or ( 3) trigger a view change (4c or 4d below).
3. 3. timeout and view change cases
Cases 4a and 4b allow a client c’s request to complete with
2f + 1 to 3f + 1 matching responses. However, if the primary
or network is faulty, c may not receive matching spec-response or local-commit messages from even 2f + 1 replicas. Cases 4c and 4d therefore ensure that a client’s request
either completes in the current view or that a new view with
a new primary is initiated. In particular, case 4c is triggered
when a client receives fewer than 2f + 1 matching responses
and case 4c occurs when a client receives responses indicating inconsistent ordering by the primary.¶
4c. Client receives fewer than 2f + 1 matching
SPEC-RESPONSE messages and resends its request to
all replicas, which forward the request to the primary in order to ensure that the request is assigned
a sequence number and eventually executed.
A client sets a second timer when it first issues a request.
If the second timer expires before the request completes,
the client suspects that the primary may not be ordering
requests as intended, so it resends its request message
through the remaining replicas so that they can track the request’s progress and, if progress is not satisfactory, initiate a
view change. This case can be understood by examining the
behavior of a nonprimary replica and of the primary.
Replica. When nonprimary replica i receives a message
⟨request, o, t, c⟩ from client c, then if the request has a
sc
higher time stamp than the currently cached response for
¶ Note that cases 4b and 4c are not exclusive of 4d; a client may receive messages that are both sufficient to complete a request and also a proof a misbehavior against the primary.
91 communications of the acm | november 2008 | vol. 51 | no. 11
that client, i sends a message ⟨confirm-req, u, m, i⟩ where
si
m = ⟨request, o, t, c⟩ to the primary p and starts a timer. If
sc
the replica accepts an order-req message for this request
before the timeout, it processes the order-req message as
described above. If the timer fires before the primary orders
the request, the replica initiates a view change.
Primary. Upon receiving the message ⟨confirm-req, u,
m, i⟩ from replica i, the primary p checks the client’s time
si
stamp for the request. If the request is new, p sends a new
order-req message using a new sequence number as de-
scribed in step 2.
Additional Pedantic Details: If replica i does not receive the
order-req message from the primary, the replica sends the
confirm-req message to all other replicas. Upon receipt
of a confirm-req message from another replica j, replica
i sends the corresponding order-req message it received
from the primary to j; if i did not receive the request from the
client, i acts as if the request came from the client itself. To
ensure eventual progress, a replica doubles its current timeout in each new view and resets it to a default value if a view
succeeds in executing a request.
Additionally, to retain exactly once semantics, replicas maintain a cache that stores the reply to each client’s most recent
request. If a replica i receives a request from a client and the
request matches or has a lower client-supplied time stamp than
the currently cached request for client c, then i simply resends
the cached response to c. Similarly, if the primary p receives an
old client request from replica i, p sends to i the cached order-req message for the most recent request from c. Furthermore,
if replica i has received a commit certificate or stable checkpoint for a subsequent request, then the replica sends a local-commit to the client even if the client has not transmitted a
commit certificate for the retransmitted request.
4d. Client receives responses indicating inconsistent ordering by the primary and sends a proof of
misbehavior to the replicas, which initiate a view
change to oust the faulty primary.
If client c receives a pair of spec-response messages
containing valid messages OR = ⟨order-req, u, n, h , d, ND⟩
n
sj for the same request (d = H(m) ) in the same view u with dif-
fering sequence number n or history h or ND, then the pair
n
of order-req messages constitutes a proof of misbehavior2
(POM) against the primary. Upon receipt of a POM, c sends a
message ⟨pom, u, POM⟩ to all replicas. Upon receipt of a valid
sc
pom message, a replica initiates a view change and forward
the pom message to all other replicas.
4. eVaLuation
This section examines the performance of Zyzzyva and compares it with existing approaches. We run our experiments
on 3.0 GHz Pentium- 4 machines with the Linux 2. 6 kernel.
We use MD5 for hashing and UMAC4 for message authentication codes (MACs). MD5 is known to be vulnerable, but
we use it to make our results comparable with those in the
literature. Since Zyzzyva uses fewer MACs per request than
any of the competing algorithms, our advantages over other
