Consensus

Why processes must agree

Components may hold divergent views of the system state and of what is happening. Coherent behaviour then requires them to agree on everything relevant (state, events…). What matters is that they reach the very same conclusion, whatever it is about.

Examples of agreement problems [Fischer, 1983]

1. Distributed database: commit or abort a distributed transaction?
2. Replicated file system: where should the file copies reside?
3. Flight control: the engine and flight-surface control modules must agree whether to continue or abort a landing.

When processes fail, the reliable ones must agree on what has happened and what happens next, so that state and evolution stay consistent, e.g. during recovery (Ch. 4). So consensus is essential to fault tolerance: when a crash breaks replica synchronisation, recovery needs the replicas to agree on each replica's state and on the events handled or still to handle.

Consensus is often hidden inside other problems: commit (§3), replication (Ch. 5), replicated state machines (§7), coordinator election (Ch. 2) and ledgers (Ch. 7). Reducing so many issues to one abstract problem gives general solutions. “…how hard can this be?”

The model: processes, time, failures

A system is modelled as a collection of processes (logical) or processors (physical) that compute at the same time and interact through:

1. one-to-one direct channels: message-passing architectures;
2. shared channels: shared-memory architectures.

Concurrent or distributed, process or processor, even parallel: the literature uses them interchangeably when the problem is unaffected by its physical nature (precise terms: Ch. 1).

A crashed process and a slow one both look silent. Waiting for it may never end; deciding without it risks contradicting a decision it is about to make.

Failure model: processes, processors and links may all fail, in diverse ways. Fault tolerance is the property of keeping working beyond faults of any sort (Ch. 4).

The problem, precisely

As stated, “always output 0” would work. So dependency requirements say how y must depend on the inputs, and each choice defines a different problem:

Dependency requirements [Fischer, 1983]

1. Non-triviality: for each y ∈ {0, 1}, some input vector and run lead to y.
2. Strong unanimity: if x_i = x for all i, then y = x.
3. Weak unanimity: the same, required only if no failures occur at run time.

Two relatives change what is agreed on:

The concrete case is transaction commit [Dolev & Strong, 1982]: the data managers of a transaction agree whether to install its results or discard them (say, because one could not do its part). All must decide the same, or the database becomes inconsistent.

For Paxos the slides use today's names. Agreement: no two processes decide differently. Validity: the decided value was proposed. Termination: every non-faulty process eventually decides. The first two are safety, the third liveness.

With reliable processes and network, commit is straightforward. Real systems suffer faults [Fich & Ruppert, 2003]:

1. process crashes;
2. network partitioning;
3. lost, distorted or duplicated messages;
4. Byzantine failures, where faulty processes go out of control or behave malevolently.

Enough faults overwhelm any protocol, so the goal is tolerating a prescribed number of “expected” ones.

FLP: impossible with one crash

Fich & Ruppert survey “hundreds” of impossibility results, outright or within resource bounds, across models of synchrony, fault tolerance, communication and randomisation. CAP is not alone (Ch. 5):

Impossibility, again

1. Distributed systems are easy to conceive and build, easy to crash, hard to understand and debug.
2. Formal proofs are fundamental for serious engineering, yet properties are difficult to prove.
3. So we must know how models affect properties, and what we cannot solve.

The other hypotheses are kind: no Byzantine failures, reliable exactly-once delivery. Still, one process stopping at an inopportune time can defeat any commit protocol. Without further assumptions, or tighter limits on the failures tolerated, there is no robust solution.

What the proof shows

A configuration (all process states plus the messages in transit) is univalent (0- or 1-valent) if only one decision is still reachable from it, and bivalent if both are. For a deterministic protocol, the proof has two steps:

1. Some initial configuration is bivalent (Fig. 6.1): the inputs alone do not fix the outcome; the schedule does.
2. Bivalence can last forever. From a bivalent configuration, any pending step can be taken, possibly after others, and still reach a bivalent configuration. That yields an infinite run where every process keeps stepping and every message arrives, yet nobody decides.

FLP shows that a bad run exists for every such protocol, not that it is likely.

From impossible to possible

Give up the problems, or essential features of the systems solving them? The slides choose a third road: solutions within the boundaries impossibility theorems set, following Howard's “making impossible possible”:

Solution to FLP [Howard, 2016]

1. In practice: accept that the system will sometimes be unavailable, and mitigate that with timers and backoffs.
2. In theory: make weaker assumptions about synchrony, e.g. “messages arrive within a year”.

Neither refutes FLP. A timer only guesses that a silent process crashed, so a wrong guess must cost time, never safety; and assuming some bound, however large, suffices to prove eventual decision. Paxos is built on this split.

Paxos

Lineage

1. A 1989 technical report by Lamport, recast in a more academically viable form as “The part-time parliament” [Lamport, 1998].
2. Generalised with respect to state machine replication [Lampson, 1996].
3. Formally described and proven correct [De Prisco et al., 1997].
4. Nicely explained in “Paxos made simple” [Lamport, 2001].

Features

1. Paxos implements fault-tolerant consensus on a single value.
2. It runs on a completely connected network of n processes and tolerates up to f failures, with n ≥ 2f + 1.
3. Processes can crash and messages may be lost. Byzantine failures are ruled out.
4. It primarily guarantees agreement and validity.
5. Termination is ensured only if there is a sufficiently long interval in which no process restarts the protocol.

Items 4 and 5 are the answer to FLP: safety is unconditional, liveness is conditional.

Process roles

1. Proposer: submits proposed values on behalf of clients.
2. Acceptor: decides the candidate values for the final decision.
3. Learner: collects this from the acceptors and reports the final decision back to the clients.

Roles are logical processes [Tanenbaum & van Steen, 2017]: one process may play all three. The basic idea is a two-phase process (promise, then commit), majority agreement and monotonically increasing numbers labelling proposals.

Why two phases

Paxos made simple [Lamport, 2001]

1. Values are proposed by proposers.
2. There is not one acceptor but several, an odd number.
3. Quorum: once a bare majority of acceptors accepts a value, it is chosen.
4. Once a value is chosen, future proposals must propose the same value.
5. Hence two phases: prepare finds out whether a value may already be chosen, and accept proposes accordingly.
6. The result is either a chosen value or another iteration, which in theory might lead to livelock.

One acceptor's crash would stop everything, hence several. A majority suffices because any two majorities share at least one acceptor, and with 2f + 1 acceptors a majority survives f crashes. Hence n ≥ 2f + 1, and an odd number: a (2f + 2)-th acceptor enlarges the majority without tolerating another crash.

Point 4 is the core. A proposer cannot see whether a value was chosen: acceptances may be lost or sit on crashed acceptors. So it first asks a majority what they accepted, and makes them promise to ignore older proposals so the answer cannot go stale. That majority overlaps any choosing majority, so the chosen value (or a later proposal carrying it) is among the replies, and adopting the highest-numbered one suffices.

The phases [Ghosh, 2014]

Proposals

1. A proposal is a pair (v, n): a value and a sequence number.
2. To deal with crashes, multiple acceptors are selected for the proposal.
3. A proposal must be endorsed by at least one acceptor before it becomes a candidate for the final decision.
4. The sequence number distinguishes successive attempts to invoke the protocol.
5. On receiving a proposal with a larger sequence number from a given process, acceptors discard those with lower numbers.
6. Eventually, an acceptor accepts the majority's choice.

Phases

1. Preparatory phase. Each proposer sends (v, n) to each acceptor. If n is the largest number an acceptor has seen, it replies ack(n, ⊥, ⊥), a promise to ignore proposals numbered below n. If it has already accepted (v, n′) with n′ < n, it replies ack(n, v, n′).
2. Request for acceptance. A proposer with acks from a majority sends accept(v, n) to all acceptors. If any ack carried a value, v must be the one with the highest number (rule 2.1). An acceptor accepts unless it has promised some n′ > n.
3. Final decision. A value accepted by a majority becomes the decision. The acceptors multicast it to the learners, which check the majority and tell the clients.

Ghosh's observations turn these rules into the two invariants behind safety:

1. An acceptor accepts proposal n only if it has not promised any n′ > n.
2. If accept(v, n) is sent, then either no acceptor in some majority has accepted any n′ < n, or v is the value of the highest-numbered such proposal accepted in that majority.

Duelling proposers and leaders

Scenario 4 is point 6's livelock. Promises for 2 make P1's accept for 1 ignored; P1 retries with 3, making P2's accept ignored; and so on. Every rule holds and nothing is chosen: FLP's endless run, made concrete. The remedy is a distinguished proposer, a leader, plus timers and backoffs. This reduces conflicts without eliminating them: electing a leader is itself agreement, so two processes may briefly both believe they lead. That costs progress, never safety.

From one value to a replicated log

1. The same state machine is replicated over a distributed system.
2. Each replica has a consensus module.
3. An operation is performed on a replica only if and when all machines have agreed on the same order of execution.
4. Consensus over distributed state becomes consensus over distributed actions on state.
5. Determinism is assumed.

Determinism makes the shift sound: same start, same operations, same order, same state. It is the replicated bank account of Ch. 2, fixed by agreement rather than clocks.

Multi-Paxos [Van Renesse & Altinbuken, 2015]

1. SMR needs consensus over an array of values; Paxos handles one.
2. Multi-Paxos runs one separate, indexed Paxos instance per array entry,
3. plus leader election to reduce proposer conflict, presumably dropping iterations.
4. It is not really well specified overall.

Other Paxos-based algorithms

1. Fast Paxos [Lamport, 2006]: proposers send values straight to the acceptors, bypassing the leader. Without conflicts this saves a message delay, at the price of larger quorums.
2. ZooKeeper [Hunt et al., 2010]: a coordination service.
3. ZAB, ZooKeeper atomic broadcast [Reed & Junqueira, 2008].
4. Egalitarian Paxos [Moraru et al., 2013]: leaderless.
5. Raft [Ongaro & Ousterhout, 2014]: designed to be understandable, with a strong leader.

Chubby. Google built a Paxos-based fault-tolerant database [Chandra et al., 2007] for Chubby [Burrows, 2006], a reliable lock service used widely inside Google, e.g. by GFS and Bigtable. They use Chubby; Chubby runs Paxos. Ledgers take the same state-machine idea to open, Byzantine settings (Ch. 7).

Lessons

General

1. Impossibility results define the space of problems we can actually solve.
2. Relating formal models to their practical instances often reveals a technically feasible solution.
3. Formal models are essential to sound engineering of distributed systems, and not just in very complex settings.

Specific

1. Faults are both the source of the problems of distributed systems and the reason we need them.
2. Consensus is one of the most expressive and general ways to model distributed application problems.
3. Its complexity defies common sense and yields archetypal impossibility results.
4. Yet protocols solve it in meaningful cases by relaxing some hypotheses: Paxos & friends.