based on LL/SC
and order them. Then it proposes seq
to the consensus instance SC[k]. This
instance returns a sequence saved in
resi, which is added by pi at the end of
its local queue to_deliverablei.
When are Universal
An impossibility. A fundamental result in distributed computing is the
impossibility to design a (
deterministic) algorithm that solves consensus
in the presence of asynchrony, even if
only one process may crash, either in
message-passing or read/write shared
16 Given that consensus and TO-broadcast are equivalent,
the state machine replication algorithm presented above cannot be implemented in asynchronous systems
where processes can crash.
Thus, sequential thinking for concurrent computing has studied properties about the underlying system that
enable the approach to go through.
There are several ways of considering
computationally stronger (read/write
or message-passing) models,
35, 37 where
state machine replication can be implemented. Some ways, mainly suited
to message-passing systems, are presented in the sidebar “Circumventing
Consensus Impossibility.” Here, we
discuss a different way, through powerful communication hardware.
Systems that include powerful objects. Shared memory systems usually
include synchronization operations
such as Test&Set, Compare&Swap, or
the pair of operations Load Link and
Store Conditional (LL/SC), in addition to read/write operations. These
operations have a consensus number
greater than 1. More specifically, the
consensus number of Test&Set is 2,
while the consensus number of both
Compare&Swap and the pair LL/SC, is
+∞. Namely, 2-process (but not a 3-pro-
cess) consensus can be implemented
from Test&Set, despite crash failures.
Compare&Swap (or LL/SC) can implement consensus for any number of
processes. Hence, for any n, any object can be implemented in an asynchronous n-process read/write system
enriched with Compare&Swap (or LL/
SC), despite up to n− 1 process crashes.
Furthermore, there are implementations that tolerate arbitrary, malicious
State machine replication based on
LL/SC. To give more intuition about
state machine replication, and further-
more, about the way that blockchains
work, we present an implementation
based on LL/SC. (Another option is
based on Compare&Swap, but it is not
“self-contained” in the sense it has to
deal with the ABA problem.
The intuition of how the LL/SC operations work is as follows. Consider a
memory location M, initialized to ⊥, accessed only by the operations LL/SC. Assume that if a process invokes
Algorithm 6. Implementing a consensus object CONS from the operations LL/SC.