Distributed systems are hard: as a running theme of this part of the course, they “do not work in theory, but work in practice.” The reason is that every protocol strikes a balance between the assumptions it is willing to make about the environment and the guarantees it can then deliver. There is no universal solution; understanding a protocol means, first of all, understanding the assumptions under which it operates.

This chapter is about agreement: getting a set of distributed processes to agree on something despite failures. We first recall the general consensus problem and the algorithms that solve it under idealised assumptions (FloodSet for crash failures, Byzantine agreement for malicious ones, and the FLP impossibility that limits both). We then move to agreement in practice, studying the protocols that real systems actually run: the commit protocols 2PC and 3PC for atomic transactions across a partitioned database, the Raft protocol for replicated state machines, and the blockchain approach to agreement in an open, adversarial network. Each is a different point in the same design space, chosen for a different set of assumptions.

1. The Consensus Problem#

1.1 What Agreement Means#

Distributed agreement sits at the intersection of two problems seen before: synchronisation between parties and reaching a decision in the presence of failures. In the general consensus problem, each process starts with an initial value and the processes must jointly decide on a single value. A correct consensus protocol satisfies three properties:

1.2 Assumptions and Failure Models#

Whether consensus is solvable at all, and by which algorithm, depends entirely on three orthogonal assumptions:

Assumption	Benign end	Hard end
Timing	Synchronous (bounded delays; a timeout detects a crash for certain)	Asynchronous (unbounded delays; a slow process is indistinguishable from a crashed one)
Channels	Reliable (messages eventually delivered, uncorrupted)	Unreliable (messages may be lost or duplicated)
Process failures	Crash / omission (a process stops, but never lies)	Byzantine (a process may send arbitrary, even malicious, messages)

Two facts frame everything that follows. First, if links are unreliable (messages can be permanently lost), consensus is impossible: any protocol that agrees after $n$ messages must also agree after $n-1$ (in case the last is lost), and by induction after zero messages, which is absurd. Consensus therefore requires reliable links (or TCP to make them so). Second, and more subtly, even with reliable links and only crash failures, consensus is impossible in a fully asynchronous system, as the FLP result below states.

1.3 FLP Impossibility#

FLP is not a counsel of despair. It says that no protocol can guarantee both safety and liveness in the asynchronous model in theory; in practice, protocols circumvent it by adopting the synchrony assumption, treating a sufficiently long timeout as evidence of a crash. This is untrue in the strict sense, but with generous timeouts it works reliably, and it is the escape hatch that every practical protocol in this chapter uses.

1.4 FloodSet: Consensus Under Crash Failures#

Assume the benign end of every axis: a synchronous system, reliable channels, and only crash failures, tolerating up to $f$ crashes. Under these assumptions a clean algorithm exists, the FloodSet algorithm.

The algorithm. Every process keeps a set of values, initialised with its own starting value. In each round, every process broadcasts its entire current set to all others, then merges all received sets into its own. The protocol runs for exactly $f+1$ rounds. At the end, every survivor holds an identical set; if it is a singleton, that value is the decision, otherwise all processes apply the same pre-agreed deterministic rule (e.g. take the minimum) and, because the sets are identical, choose the same value.

Correctness of FloodSet

Let $f$ be the maximum number of crashes.

• Termination is immediate: the protocol runs a fixed number of rounds ($f+1$) and then decides.
• Validity: if all processes start with $v$, the only value ever in circulation is $v$, so every set stays $\{v\}$ and the decision is $v$.
• Agreement is the crux. At most $f$ processes crash, and each crashes in exactly one round, so among the $f+1$ rounds there is at least one crash-free round $r$ (pigeonhole). During round $r$ no process fails mid-broadcast, so every process still alive sends its full set to all and, by reliability and synchrony, every message is delivered. Hence after round $r$ all surviving processes hold the same set $W^\*$ (the union of everything alive at the start of $r$). In every later round no new value can appear (a process only adds values it receives, and all sets already equal $W^\*$), so the sets stay identical through round $f+1$. Identical sets plus the same deterministic decision rule yield the same decision. $\blacksquare$

Why every assumption is fundamental. Each assumption can be dropped only at the cost of correctness, and the counterexamples are instructive (they are exactly what an exam question on FloodSet asks for):

• Bounded crashes ($\le f$). If a crash can occur in every round, no round is guaranteed crash-free, so survivors may hold different sets and disagree. The algorithm cannot tolerate an unbounded number of crashes: that would require infinitely many rounds. In practice one fixes $f$ and accepts that more than $f$ crashes void the guarantee.
• Synchrony. Without bounded rounds there is no notion of “round $f+1$”: a process cannot tell a crashed peer from a slow one and does not know when a round has ended. This is FLP again.
• Reliable channels. If a message may be lost, the last-message induction of Section 1.2 applies and consensus is impossible.
• Crash (not Byzantine) failures. A Byzantine process can send different sets to different peers, so the “everyone computes the same union” step of the proof collapses; a stronger and more expensive algorithm is needed (Section 1.5).

An easy optimisation removes most of the traffic: broadcast the whole set only in the first round, and thereafter re-broadcast only when a process first learns a new value. Correctness is preserved because the crash-free-round argument is unaffected.

1.5 Byzantine Agreement#

When processes may behave arbitrarily rather than merely stop, consensus becomes much harder. This is the Byzantine Generals Problem (Lamport et al.): loyal generals must agree on a plan while some traitors send conflicting messages. The requirements are the same three properties restricted to non-faulty processes.

This $3m+1$ requirement is stricter than the $2m+1$ needed when an external client merely queries a group and takes a majority vote, because here the faulty processes are inside the deliberation and can mislead different members differently.

Lamport's algorithm for 4 generals, 1 traitor

Framed as generals announcing troop strengths and agreeing on the total: (1) each process sends its own value to all others; (2) each builds a vector of the values it received; (3) each sends its vector to all others; (4) each computes, position by position, the majority of the vectors it now holds. Because a Byzantine process may report different values to different peers, the position-wise majority over enough correct processes neutralises its influence. With $3$ generals and $1$ traitor there are only $2$ loyal votes per position, so no majority forms and agreement is impossible; $3m+1$ total (hence $2m+1$ loyal) is exactly what restores a clean majority.

The group-size requirements are worth tabulating side by side, since crash and Byzantine tolerance differ sharply:

Scenario	Fault type	Nodes for $k$-fault tolerance
External client querying a group	Crash	$k+1$
External client querying a group	Byzantine	$2k+1$
Internal group consensus	Crash	$k+1$
Internal group consensus	Byzantine	$3k+1$

With the theory in place, we now turn to the protocols that production systems actually run.

2. Commit Protocols#

2.1 ACID and the Atomicity Problem#

Relational databases provide ACID transactions: Atomic, Consistent, Isolated, Durable. Commit protocols are the mechanism that enforces atomicity: a transaction ends in exactly one of two states, either all its changes are made durable and visible, or none are. There is no in-between.

Atomicity becomes hard when the database is partitioned (sharded) across machines. The canonical example is a money transfer between two accounts held on two different machines: withdraw from account $A$ on machine 1, deposit to account $B$ on machine 2, preserving the integrity invariant that no account goes below zero. Either both changes are applied or neither is. This is a matter of agreement: the two sides must agree on whether to commit or abort.

2.2 Atomic Commit Versus Consensus#

Atomic commit is a specialised consensus problem, and the specialisation matters:

	Consensus	Atomic commit
Inputs	one or more nodes propose a value	every node votes commit or abort
Decision rule	agree on one proposed value	commit iff all vote commit, else abort
Failure handling	tolerates failures while a majority survives	any crash forces an abort

The rule is therefore veto-based: a single ABORT vote, or a crash treated as an implicit abort, is enough to abort everything.

3. Two-Phase Commit (2PC)#

Two-Phase Commit is by far the most widely used commit protocol: if a database provides atomicity, it almost certainly runs 2PC or a variant. It uses two roles: a coordinator that manages the global decision, and the participants that hold the partitions. The coordinator may or may not also be a participant, a distinction that turns out to be decisive for failure handling.

3.1 Normal Operation#

Phase 1 (voting). The client sends the transaction to all participants and tells the coordinator to begin 2PC. The coordinator sends PREPARE to all participants. Each participant votes COMMIT if the transaction is valid from its perspective (e.g. the account has sufficient funds), or ABORT otherwise.

Phase 2 (decision). If the coordinator collected COMMIT from all participants, it sends GLOBAL COMMIT; if any voted ABORT, it sends GLOBAL ABORT. Each participant then applies or rolls back accordingly.

3.2 State Diagrams#

A participant that votes ABORT may move to ABORT immediately, without waiting for the coordinator, because it already knows the global outcome must be abort. A participant that votes COMMIT, however, enters READY and must wait: it cannot know what the others voted.

3.3 Durable Storage#

Both participants and the coordinator write their decision to durable storage before acting on it, which is what makes recovery possible. If a participant crashes after voting and recovers, its vote is still on disk. If the coordinator has logged GLOBAL COMMIT and then crashes, on recovery it can re-send the decision to any participant that missed it. The durability of the decision is exactly the “D” of ACID, and it guarantees that the coordinator’s log and the participants’ logs eventually agree on the same outcome.

3.4 Handling Failures and the Blocking Problem#

Failure detection relies on the synchrony assumption: after a timeout with no response, the node is presumed failed.

A participant fails. If a participant does not respond in phase 1, the coordinator times out and issues GLOBAL ABORT, which is safe: a missing vote means no commit could have been reached, and the participant learns the abort on recovery. If a participant fails after the decision is on the coordinator’s durable storage, it simply reads the outcome from the coordinator when it recovers.

The coordinator fails. This is the dangerous case. Consider a waiting participant:

• In INIT (never voted): the coordinator cannot have committed, since this vote is missing. Safe to abort.
• In READY (voted commit, awaiting the decision): it does not know the outcome and cannot decide alone. It may contact other participants:
  • a peer in COMMIT/ABORT → copy that decision (the coordinator had decided before crashing);
  • a peer in INIT → some node never voted → safe to abort;
  • all peers in READY → blocked: no safe decision exists.

The block is real precisely when the coordinator is also a participant (typical, to reuse nodes). Then every survivor in READY voted commit, but nobody knows what the coordinator voted before crashing: if it logged commit, aborting violates atomicity; if it logged abort, committing does. No safe decision can be made without it.

3.5 Safety Versus Liveness#

Every protocol balances two properties, and by FLP it cannot guarantee both in an asynchronous system:

Property	Meaning
Safety	the protocol always does what it promises (here: atomicity, all-or-nothing)
Liveness	the protocol always makes progress and eventually terminates

2PC chooses safety over liveness. It is always atomic, but it can block, and a single node failure (the coordinator) is enough to halt it. This is a practical, not academic, problem, for three reasons. First, a single failure suffices, so it is not rare. Second, 2PC is on the critical path: it is often the most time-consuming part of a distributed transaction, and while it runs, all concurrency-control locks are held, so a blocked coordinator stalls every other transaction. Third, failover is expensive: in an asynchronous system you cannot be sure the coordinator crashed rather than being slow, and electing a replacement risks a conflict if the original returns; historically this has sometimes required manual intervention.

4. Three-Phase Commit (3PC)#

4.1 The Idea: A Pre-Commit State#

We want a non-blocking protocol, one that does not stall when a single node fails. There is always a price: more liveness costs more communication. Three-Phase Commit pays it by adding one round. Its key idea is to split the commit into two steps: first tell everyone the outcome (they enter a pre-commit state), and only after everyone acknowledges knowing it do they actually commit. This intermediate state is what lets a survivor reason about the global outcome even when the coordinator has failed, something impossible in 2PC.

4.2 Operation#

Phase 1 is exactly as in 2PC; any ABORT still triggers GLOBAL ABORT immediately, because aborting is never problematic. If all vote COMMIT, the coordinator does not commit directly: it sends PRE-COMMIT, waits for all acknowledgements (so it knows every node knows the outcome), and only then sends GLOBAL COMMIT.

4.3 Handling Failures#

A participant fails. If the coordinator is still in WAIT, it times out and issues GLOBAL ABORT (as in 2PC). If it is in PRE-COMMIT, it may safely commit and inform the failed participant on recovery, because reaching pre-commit means everyone (including the failed node) had already voted commit.

The coordinator fails. A participant in INIT aborts safely (it never voted). A participant in READY contacts others:

Other participant’s state	Conclusion
ABORT	someone aborted or received a global abort → abort
INIT	some node never voted → abort
PRE-COMMIT	that node saw the commit outcome → safe to commit
all in READY	quorum decision needed (below)

The improvement over 2PC: the pre-commit state acts as a witness. In 2PC, all-in-READY was an unresolvable block; in 3PC, if even one peer is in PRE-COMMIT we know the decision was commit.

4.4 Quorum-Based 3PC and Partitions#

With several failures or a network partition, “ask any peer” is unsafe: two disconnected groups could decide differently. The quorum-based variant requires a majority before any decision. With $2n+1$ nodes a majority needs $n+1$, and only one majority can exist at a time.

What the majority observes	Decision
at least one node in PRE-COMMIT	commit (the outcome was already communicated; no other majority can differ)
all in READY, none in PRE-COMMIT	abort (no outcome was ever sent; even a returning coordinator cannot be in commit without first passing pre-commit)

Crucially, pre-commit is not a final decision. If a minority holds a node in pre-commit while the majority aborts, the abort simply propagates when the partition heals: pre-commit can always be overridden by a global abort, and no safety violation occurs. Liveness holds as long as a majority is connected; a minority cannot serve full transactions (it lacks the data), but the majority partition keeps functioning.

4.5 Why 3PC Is Not Used in Practice#

3PC is theoretically superior, yet virtually no production database runs it. The reason is cost. The commit protocol is on the critical path of every transaction, so every transaction pays the full price: 2PC needs 2 network rounds, 3PC needs 3, a 50% overhead. Meanwhile hardware failures are genuinely rare (a machine might fail once in years), so paying 50% more on every transaction to handle a scenario that occurs a handful of times a year is not worthwhile. The blocking problem of 2PC is instead solved differently: by making the coordinator itself fault-tolerant through replication (Section 6.10), and by optimising for specific workloads.

5. The CAP Theorem#

The tradeoffs above are captured by the CAP theorem (early 2000s): a distributed data store cannot simultaneously guarantee all three of consistency, availability, and partition tolerance.

Letter	Property	Meaning
C	Consistency	the store behaves as a single up-to-date copy on one machine
A	Availability	it can always respond to reads and writes (liveness)
P	Partition tolerance	it keeps working despite network partitions

Because network partitions are outside the engineer’s control, partition tolerance is not optional, so the practical choice for any real system is to sacrifice either strong consistency or high availability. This is the same safety-versus-liveness tradeoff seen throughout: the extreme of consistency (a distributed system that behaves exactly like one machine) is achievable only at a cost no one is willing to pay on every operation. The later chapter on replication and consistency explores the rich spectrum of options in between.

6. State Machine Replication and Raft#

6.1 A Different Problem: Replication, Not Partitioning#

Commit protocols dealt with a partitioned database, where different data live on different nodes and must commit atomically together. We now switch to replication: every node holds an identical copy of the same state. The goal is resilience to failure while giving clients the illusion of a single, reliable machine. This is proper consensus, and the standard formulation is State Machine Replication.

6.2 The Problem: A Replicated Log#

The shared state is, say, a key-value store with variables $x$ and $y$, replicated across (typically) five nodes. Clients read and write, and must experience the cluster as a single consistent machine even as nodes fail. Formally, operations must be linearizable: all clients and servers agree on one sequential order of operations, as if executed one at a time on one machine.

The central data structure is the log: each node stores not just the current state but the ordered sequence of every operation applied. The safety guarantee is that all non-failing nodes hold the same log; the state is just the result of replaying it. Replication buys fault tolerance: with $2n+1$ nodes the system tolerates $n$ failures (five nodes tolerate two). A majority is required rather than a single survivor because, under partitions, two disconnected groups could otherwise process different operations and diverge; requiring a majority ensures at most one group can decide at any time, since two majorities cannot coexist.

6.3 Failure Model and Guarantees#

Raft (and Paxos) operate under the most general failure model: no Byzantine failures, but durable storage for recovery, an asynchronous and unreliable network (messages may be delayed, lost, or duplicated, with no timing guarantees), and any kind of partition. Membership is assumed fixed (adding or removing nodes is a documented extension). The guarantees are:

Property	Description
Safety	all non-failing nodes execute the same commands in the same order
Liveness	while a majority is up and can communicate, the system makes progress

By FLP, both cannot hold together in theory; in practice Raft achieves both, because the only scenario that could block liveness (an unbounded run of split-vote elections) is engineered to be practically impossible.

6.4 A Brief History: Paxos and Raft#

The classical solution is Paxos (Lamport, proposed 1989, published 1998 as The Part-Time Parliament), the reference consensus algorithm for roughly three decades. Basic Paxos agrees on a single decision; a replicated log needs multi-Paxos. Paxos is famously hard to understand and to implement correctly, so every team implemented it differently, with bugs. Raft (Ongaro and Ousterhout, 2014) was designed for one explicit goal, understandability. It is equivalent to multi-Paxos in assumptions, guarantees, and performance; it does not do better in theory, it does the same thing more clearly, by decomposing the problem into independent concerns. Raft was proved correct with a theorem prover, has clean reference implementations, and has become the de facto standard.

Raft splits consensus into three concerns: log replication (normal operation), leader election (recovering from a failed leader), and log consistency (keeping logs correct across leader changes).

6.5 Log Replication: Normal Operation#

At any moment each node is a follower (passive, receives entries), a candidate (a follower running for election), or the single leader (receives all client commands and drives replication). All nodes start as followers.

The steps: (1) a client sends a command (e.g. write x = 5) to the leader; (2) the leader appends it to its log; (3) the leader sends the entry to all followers via AppendEntries; (4) once a majority (including itself) acknowledges, the entry is committed, meaning it is safe and permanent, guaranteed to survive any future failure; (5) the leader replies to the client; (6) afterwards, the leader tells followers to apply the entry to their state. Step 6 happens after the client reply, so from the client’s view the cost is one round trip to the leader plus the time to collect a majority of acknowledgements; in a five-node cluster that means waiting for three acknowledgements (the leader plus two). Even with no commands, the leader periodically sends empty heartbeats to signal that it is alive and to suppress unnecessary elections.

Scope of the guarantees. If so few nodes survive that no majority can form, Raft stops making progress, but this is by definition outside what consensus can solve, not a flaw. Safety holds unconditionally (no two survivors ever commit conflicting entries, however many fail); liveness holds while a majority is up and connected. With five nodes at least three must survive: if only two remain, “the other three are dead” is indistinguishable from “the other three are partitioned and deciding on their own,” so no safe decision is possible, exactly the majority reasoning of quorum-based 3PC.

6.6 Leader Election and Terms#

A follower that hears nothing from the leader for a timeout concludes the leader may be down and promotes itself to candidate, starting an election. An isolated node may start an election but simply fails to gather votes and stays unelected, while the real leader (if in a majority) keeps working.

Raft divides time into terms, numbered with consecutive integers; a new term begins with each election, and without failures a term can last for years. Every message carries the sender’s current term. Terms provide synchronisation and let nodes discard stale information: a message from a lower term is ignored, and a node that sees a higher term updates its own and, if it was leader, immediately steps down. The key invariant is at most one leader per term.

Randomised timeouts. If all followers noticed the leader’s disappearance at once and started elections simultaneously, they would split the vote and no one would reach a majority, possibly forever. Each node therefore uses a randomised election timeout (typically 150 to 300 ms), so with high probability only one node starts at a time, gathers its votes, and wins before any other times out. The range must be well above the network round-trip time so a candidate can collect votes before a competitor begins.

Voting rules. A server grants its vote to the first valid candidate it hears from and records the vote to durable storage, so it votes at most once per term even across crashes and two candidates cannot both win a term. A candidate is valid only if its log is at least as up-to-date as the voter’s (Section 6.7).

Election procedure. A new candidate (1) votes for itself, (2) increments its term, (3) sends RequestVote to all; it becomes leader on a majority, steps down if it hears a valid leader with a current term, or restarts with a higher term on timeout.

FOLLOWER  → (election timeout, no heartbeat heard)     → CANDIDATE
CANDIDATE → (receives majority of votes)               → LEADER
CANDIDATE → (hears from valid leader with newer term)  → FOLLOWER
CANDIDATE → (election timeout, split vote)             → CANDIDATE (new term)
LEADER    → (discovers higher-term message)            → FOLLOWER

Example: partition and re-merge. Suppose A is leader in term 4 and a partition splits the five nodes into $\{A,B\}$ and $\{C,D,E\}$.

During the partition, A still believes it is leader and sends heartbeats to B, but cannot commit anything (it reaches only B, not a majority). On the other side, C, D, or E times out, starts term 5, and wins (three nodes). Clients that keep contacting A time out and eventually re-connect to D, which serves them normally. When the partition heals, A receives AppendEntries from D with term 5 > 4, immediately steps down to follower, adopts term 5, and A and B catch up on the entries they missed. No committed entry is ever lost or contradicted, because A committed nothing without a majority.

6.7 Log Structure and Consistency#

Each log entry records an index (its position), a term (when it was created, so entries from different leaders are distinguishable), and the command. Raft maintains the log matching property: if two entries on different servers share the same index and term, they store the same command and all preceding entries are identical. Once an entry appears at a position with a given term on two nodes, the whole prefix agrees.

Partitions can make logs diverge: a leader isolated in a minority may append entries it never commits, while the majority appends and commits new ones under a new leader. When the partition heals, the stale uncommitted entries can safely be overwritten.

The repair rides on AppendEntries, which also carries the index and term of the immediately preceding entry. If the follower matches at that position it appends and acknowledges; if not, it rejects and the leader retries one entry further back, until a common point is found, then resends everything after it, overwriting conflicting uncommitted entries. This recursion guarantees that once agreement holds at any position, all earlier positions agree too.

Committed entries are permanent. A committed entry (acknowledged by a majority, client notified) is never overwritten by a future leader. This is enforced by the voting restriction: a candidate must prove its log is at least as up-to-date, meaning its last entry has a higher term, or the same term but a longer log; otherwise the voter refuses. Since any committed entry sits on a majority, and the winner needs a majority of votes, the elected leader necessarily holds every committed entry (leader completeness).

6.8 Client Interaction and Linearizability#

Clients always talk to the current leader. A client starts by contacting a random server, which redirects it to the leader for the current term. If the leader crashes, the client’s request times out and it retries another node, which redirects to the new leader. This never violates safety: a non-leader cannot commit on its own (it cannot reach a majority), so requests to it simply time out with no side effects.

Raft guarantees linearizable semantics: operations behave as if executed exactly once, in one global order, on one copy. Because a client may retry after a leader crash without knowing whether its request already committed, each request carries a unique identifier; servers remember recently applied identifiers and discard duplicates, making operations idempotent. This is a joint responsibility: clients retry and tag; servers detect and discard.

The core algorithm extends to several practical concerns: log compaction (snapshotting the current state and discarding the log prefix that produced it), membership changes (proposing a configuration change as an ordinary log entry, with care that two majorities never coexist during the transition), and performance optimisations (batching commands, pipelining AppendEntries).

6.9 A Design Question: One Machine or Five with Raft?#

A recurring exam and design question asks whether replicating a data store across five machines with Raft, versus running it on a single well-built machine, buys performance or consistency. The intuitive “five machines must be faster” answer is wrong.

It is worth being precise about the assumptions Raft relies on, since the same question often asks for them: no Byzantine failures, and durable storage so a recovered node does not vote twice in a term. A common misconception is to list “a majority stays connected” as an assumption; it is not an assumption but the very definition of the problem’s scope, the boundary within which consensus is solvable at all.

6.10 Raft in Production: Replication Plus Partitioning#

Raft finally explains why 3PC is unnecessary. Recall that 2PC’s only fatal flaw was a single coordinator failure blocking everything. The production fix is not 3PC but to make the coordinator itself fault-tolerant with Raft.

A modern distributed database combines two layers. Layer 1 (replication, Raft): each shard is replicated across three or five nodes with Raft, producing a virtual node that behaves as a single reliable machine and never fails while a majority is up. Layer 2 (partitioning, 2PC): a transaction spanning shards uses 2PC across these virtual nodes; since each “node” is now a Raft cluster rather than a single machine, the coordinator is effectively fault-tolerant, and the catastrophic single-coordinator crash is practically impossible. For performance, replicas within a data center are colocated (same rack) so the Raft round trip is a few milliseconds; extra replicas in distant data centers provide disaster recovery without sitting on the critical path, since the local majority already suffices for correctness.

7. Byzantine Fault Tolerance and Blockchain#

7.1 The Limits of Raft’s Assumptions#

Raft assumes no Byzantine failures: all nodes follow the protocol honestly, and $2n+1$ nodes tolerate $n$ crashes. If nodes may be malicious, the mathematics changes to $3n+1$ nodes for $n$ faults (Section 1.5), giving BFT consensus protocols, structurally similar to Raft but with extra rounds to rule out deception. BFT still assumes a known, fixed membership, appropriate for trusted, closed environments but broken when the participant set is open and unknown.

7.2 Blockchain: Consensus Without Membership#

Blockchains such as Bitcoin operate in a fundamentally different setting: permissionless (anyone can join, no fixed membership, no majority to count), with potentially malicious participants, and probabilistic rather than immediate finality. The state is again a log (here a ledger): every account balance is derived by replaying all transactions from the beginning. The core threat is double spending: a malicious actor tries to spend the same coin in two conflicting transactions, creating two divergent histories and making each appear valid to a different recipient. This is a consistency problem: the log must be globally ordered so only one history is valid.

7.3 Proof of Work#

Bitcoin’s answer is Proof of Work. Instead of a trusted majority it relies on computational effort: adding a block requires solving a cryptographic puzzle that takes both the existing chain and the new block as input, which is what cryptographically links the block to the chain, with no shortcut but brute force. The puzzle is calibrated so that, across the whole network, a solution takes about ten minutes on average; the difficulty auto-adjusts to the total computing power. It is hard to solve but trivial to verify: anyone can check a proposed solution in milliseconds, and can verify the whole chain bottom-up. Special nodes called miners collect pending transactions into a candidate block and race to find the proof; the winner broadcasts the block and is rewarded with newly minted bitcoins (the incentive to participate). Because a solution takes substantial time and computation, two nodes almost never produce conflicting valid blocks at once, so sustaining two divergent chains is very hard.

7.4 The Longest Chain Rule and the 51% Attack#

When two valid chains compete (e.g. a near-simultaneous solution), honest nodes adopt the longest chain, since it embodies the most accumulated work (a deterministic tie-break settles equal lengths). Because no node can be sure no longer chain exists elsewhere, finality is probabilistic: the deeper a transaction sits, the safer it is, because reversing it would require producing a longer alternative chain, out-computing the rest of the network. This is why a merchant waits for enough confirmations (blocks built on top) before shipping goods: it is waiting for the reversal probability to become negligible.

Safety breaks only in the 51% attack: an entity controlling more than half the network’s compute can consistently outpace everyone and forge a longer chain. Bitcoin’s security therefore assumes no single entity accumulates that much power, which holds when participation is genuinely decentralised. The comparison with Raft crystallises the theme of the whole chapter, that different assumptions yield radically different protocols:

Property	Raft	Blockchain (Bitcoin)
Membership	fixed, known	open, permissionless
Failure model	crash only	malicious actors allowed
Finality	immediate (once committed)	probabilistic (grows with depth)
Throughput	high (ms per commit)	low ($\sim$ 10 min per block)
Trust model	majority of nodes honest	majority of compute honest
Sybil resistance	membership control	proof of work

8. Recap#

Theme	Key point
Consensus (theory)	agreement + validity + termination; solvable under crash + synchronous + reliable links
FloodSet	$f+1$ rounds tolerate $f$ crashes; correctness rests on one crash-free round
Byzantine	needs $3m+1$ nodes to tolerate $m$ malicious; FLP forbids async consensus in theory
2PC	veto-based atomic commit; safe but blocks on a single coordinator crash
3PC	pre-commit witness removes the block; unused because of a 50% round-trip overhead
CAP	with partitions unavoidable, trade consistency against availability
Raft	leader + replicated log; majority-committed entries are permanent; linearizable
Raft vs 1 machine	no latency/consistency gain, only fault tolerance
Production	Raft-replicated shards as virtual nodes, 2PC across them
Blockchain	permissionless consensus via proof of work; probabilistic finality; 51% attack

9. Exam Questions#

The following questions are drawn from past exams. Worked solutions are unofficial: the instructor does not publish official solutions, so these are our own reconstructions and may contain errors.

Solution

Problem. FloodSet solves consensus: $n$ processes, each with an initial value, must all decide the same value (agreement), decide their common value if they all started equal (validity), and eventually decide (termination).

Algorithm. Each process keeps a set, initialised to its own value. For $f+1$ rounds, every process broadcasts its whole set to all others and merges what it receives. After round $f+1$ all survivors hold the same set; decide its single element, or apply a fixed deterministic rule (e.g. minimum) if several remain.

Assumptions: synchronous system, reliable channels, crash (not Byzantine) failures, at most $f$ of them.

Why each is fundamental (counterexamples).

• At most $f$ crashes. Suppose $f=1$ but two processes crash. With one crash per round there may be no crash-free round: process A crashes in round 1 after telling only B its value; B crashes in round 2 after telling only C; C ends holding a value that D never saw. Survivors disagree.
• Synchrony. Without bounded rounds a process cannot tell a slow peer from a crashed one, so “round $f+1$” is undefined and the pigeonhole argument fails (FLP).
• Reliable channels. If the last message of an agreeing run can be lost, the induction of the lecture shows agreement is impossible with lossy links.
• Crash, not Byzantine. A Byzantine process can send different sets to different peers, so survivors no longer compute the same union and agreement breaks; $3m+1$ nodes and a Byzantine algorithm would be required.

Correctness. Termination: fixed $f+1$ rounds. Validity: if all start with $v$, only $v$ ever circulates. Agreement: at most $f$ crashes over $f+1$ rounds leaves at least one crash-free round $r$ (pigeonhole); in $r$ every survivor broadcasts to all and all messages arrive, so afterwards all hold the same set $W^\*$, which no later round can change. Identical sets plus the same decision rule give the same decision. $\blacksquare$

Solution

Problem. Raft solves state machine replication: it keeps an identical, identically ordered log of commands on a set of replicas, so that a client sees the cluster as a single linearizable machine that survives failures. Clients submit commands to a leader, which replicates each to a majority before committing.

Assumptions. No Byzantine failures (nodes crash but never lie); durable storage so a recovered node recalls its state and, in particular, does not vote twice in a term; an asynchronous, unreliable network (arbitrary delays, loss, duplication, any partition); fixed membership. A connected majority is not an assumption but the definition of the problem’s solvable scope.

Safety: yes, unconditionally. No two survivors ever commit conflicting entries, however many nodes fail. This rests on: at most one leader per term (a vote is durable and a majority is needed, so two leaders cannot both win a term); the log matching property; and the voting restriction (a candidate needs an up-to-date log), which guarantees an elected leader holds every committed entry, so committed entries are never overwritten.

Liveness: yes in practice, not in theory. While a majority is up and connected, Raft makes progress; randomized election timeouts ensure that, with high probability, one candidate wins quickly. In theory (FLP) an adversarial schedule of endless split-vote elections could prevent progress forever, but randomized timeouts make this practically impossible. If no majority survives, halting is correct, not a violation, because it lies outside what consensus can solve.

Solution

Response time. The single machine wins. It answers from local memory with no coordination. The Raft cluster routes every write through the leader, which must synchronously replicate to a majority before replying, and routes even reads through the leader to remain linearizable; so latency and throughput are worse, not better, than the single machine. The extra replicas are pure overhead in the normal (failure-free) case.

Consistency. Identical, and no better with Raft. A correctly implemented single machine is already linearizable, the strongest model; Raft only reproduces that behaviour across replicas, it cannot exceed it. (Weaker, higher-performance consistency models are the subject of the Replication and Consistency chapter.)

Fault tolerance. The only advantage of (b). The single machine is a single point of failure: if it dies, the store is down and data may be lost. The 5-node Raft cluster keeps serving, with committed data preserved, as long as a majority (3 of 5) is up and connected, tolerating up to 2 failures.

Bottom line. Replicating with Raft buys fault tolerance alone; it costs performance and does not improve consistency.

10. Glossary#

Term	Meaning
Consensus	processes each holding an initial value must all decide one value (agreement, validity, termination)
Atomic commit	veto-based consensus: commit iff all vote commit; any abort or crash aborts
FloodSet	crash-tolerant consensus in $f+1$ synchronous rounds of set flooding
FLP impossibility	consensus is impossible in an asynchronous system with even one crash
Byzantine failure	a process behaves arbitrarily/maliciously; needs $3m+1$ nodes to tolerate $m$
2PC	Two-Phase Commit: prepare/vote then global decision; blocks on coordinator crash
3PC	Three-Phase Commit: adds a pre-commit witness round; non-blocking but costly
CAP theorem	a store cannot have consistency, availability, and partition tolerance together
State machine replication	replicate an ordered command log so replicas act as one linearizable machine
Leader / follower / candidate	Raft node roles: the single command-driver, passive replicas, and election contenders
Term	Raft’s logical epoch; at most one leader per term; carried in every message
Log matching property	equal (index, term) entries imply equal commands and equal prefixes
Linearizability	operations appear to execute once, in one global order, on one copy
Proof of Work	permissionless agreement via a brute-force cryptographic puzzle per block
Longest chain rule	honest nodes adopt the chain with the most accumulated work; probabilistic finality
51% attack	an entity with a majority of compute power can forge a longer chain and reverse history

Compiled from G. Cugola's lectures (A.Y. 2025/26), slides + class transcriptions. Not official course material.