broadcast mechanism for reaching the
required agreement.
Total order broadcast. The TO-broadcast abstraction is an important primitive in distributed computing, which
ensures that all correct processes
receive messages in the same order.
18, 37
It is used through two operations,
TO _ broadcast() and TO _ deliver().
A process invokes TO _ broadcast(m),
to send a message m to all other processes. As a result, processes execute
TO_ deliver() when they receive a (
totally ordered) message.
TO-broadcast illustrates one more
general idea within the theory of
mastering concurrent programming
through sequential thinking: the identification of communication abstractions that facilitate building concurrent objects defined by a sequential
specification.
State machine replication based on
TO-broadcast. A concurrent implementation of object O is described
in Algorithm 4. It is a universal construction, as it works for any object O
defined by a sequential specification.
The object has operations opx(), and
a transition function δ() (assuming
δ is deterministic),where δ(state, opx
(paramx)) returns the pair ⟨state′, res⟩,
where state′ is the new state of the object and res the result of the operation.
The idea of the construction is simple. Each process pi has a copy statei of
the object, and the TO-broadcast abstraction is used to ensure that all the
processes pi apply the same sequence
of operations to their local representation statei of the object O.
Implementing TO-broadcast from
consensus. Algorithm 5 is a simple construction of TO-broadcast on top of an
asynchronous system where consensus
objects are assumed to be available.
18
Let broadcast(m) stand for “for
each j ∈ { 1, . . . , n} do send(m) to pj
end for.” If the invoking process does
not crash during its invocation, all processes receive m; if it crashes an arbitrary subset of processes receive m.
The core of the algorithm is the
background task T. A consensus object CS[k] is associated with the iteration number k. A process pi waits until
there are messages in the set pendingi
and not yet in the queue
to_deliverablei. When this occurs, process pi
computes this set of messages (seq)
Algorithm 4. TO-broadcast-based universal construction.
Algorithm 5. Implementing TO-broadcast from consensus.
Circumventing Consensus
Impossibility
Three ways of circumventing the consensus impossibility:
˲ The failure detector approach8 can abstract away synchrony assumptions
sufficient to distinguish between slow processes and dead processes.
˲ In eventually synchronous systems14 there is a time after which the processes
run synchronously. The celebrated Paxos algorithm is an example.
28
˲ By using random coins5 consensus is solvable with high probability.
˲ Often not all combinations of input values occur.
29
