are designed to allow clients and replicas to link the system’s
actions together into a single linearizable history.
3. 2. 1. Message processing details
4b. Client receives between 2f + 1 and 3f matching
responses, assembles a commit certificate, and
transmits the commit certificate to the replicas.
A client c sets a timer when it first issues a request. When
this timer expires, if c has received matching speculative
responses from between 2f + 1 and 3f replicas, then c has a
proof that a majority of correct replicas agree on the order in
which the request should be processed. Unfortunately, the
replicas, themselves, are unaware of this quorum of matching responses—they only know of their local decision, which
may not be enough to guarantee that the request completes
in this order.
Figure 2 illustrates the problem. A client receives 2f + 1
matching speculative responses indicating that a request req
was executed as the nth operation in view u. Let these responses come from f + 1 correct servers C; and f faulty servers F; and
assume the remaining f correct servers C' received an order-req message from a faulty primary proposing to execute a different request req’ at sequence number n in view u. Suppose
a view change occurs at this time. The view change subprotocol must determine what requests were executed with what
sequence numbers in view u so that the state in view u + 1 is
consistent with the state in view u. Furthermore, since up to
f replicas may be faulty, the view change subprotocol must be
able to complete using information from only 2f + 1 replicas.
Suppose now that the 2 f + 1 replicas contributing state to a view
change operation are one correct server from C, f faulty servers
from F, and f correct but misled servers from C'. In this case,
only one of the replicas initializing the new view is guaranteed
to vote to execute req as operation n in the new view, while as
many as 2f replicas may vote to execute req’ in that position.
Thus, the system cannot ensure that view u + 1’s state reflects
the execution of req as the operation with sequence number
Before client c can rely on this response, it must take additional steps to ensure the stability of this response. The client
figure 2: example of a problem that could occur if a client were to
rely on just 2f + 1 matching responses without depositing a commit
certificate with the servers.
2f+ 1 matching
(v, n, hn, ...)
h , H(req), ...), req
hn , H(req), ...), req
h’n, H(req’), ...), req’
(v, n, h’n, ...)
therefore sends a message 〈commit, c, CC〉 where CC is a com-
mit certificate consisting of a list of 2f + 1 replicas, the replica-signed portions of the 2f + 1 matching spec-response messages from those replicas, and the corresponding 2f + 1 replica
Additional Pedantic Details: CC contains 2f + 1 signatures on
the spec-response message and a list of 2f + 1 nodes, but,
since all the responses received by c from replicas are identical, c only needs to include one replica-signed portion of
the spec-response message. Also note that, for efficiency,
CC does not include the body r of the reply but only the hash
5. Replica receives a COMMIT message from a client
containing a commit certificate and acknowledges
with a LOCAL-COMMIT message.
When a replica i receives a message 〈commit, c, CC〉
containing a valid commit certificate CC proving that a re-
quest should be executed with a specified sequence number
and history in the current view, the replica first ensures that
its local history is consistent with the one certified by CC. If
so, replica i ( 1) stores CC if CC’s sequence number exceeds
the stored certificate’s sequence number and ( 2) sends a
message 〈local-commit, u, d, h, i, c〉 to c.
Additional Pedantic Details: If the local history simply has
holes encompassed by CC’s history, then i fills them as described in 3. If, however, the two histories contain different
requests for the same sequence number, then i initiates the
view change subprotocol. Note that as the view change protocol executes, correct replicas converge on a single common history, and those replicas whose local state reflect the
“wrong” history (e.g., because they speculatively executed
the “wrong” requests) restore their state from a cryptographically signed distributed checkpoint. 11
6. Client receives a LOCAL-COMMIT messages from
2f + 1 replicas and completes the request.
The client resends the commit message until it receives
corresponding local-commit messages from 2f + 1 distinct replicas. The client then considers the request to be
complete and delivers the reply r to the application.
2f + 1 local commit messages suffice to ensure that a
client can rely on a response. In particular, at least f + 1 correct servers store a commit certificate for the response, and
since any commit or view change requires participation by at
least 2f + 1 of the 3f + 1 servers, any subsequent committed request or view change includes information from at least one
correct server that holds this commit certificate. Since the
commit certificate includes 2f + 1 signatures vouching for
the response, even a single correct server can use the commit certificate to convince all correct servers to accept this
response (including the application reply and the history.)
Additional Pedantic Details: When the client first sends the
commit message to the replicas it starts a timer. If this timer