Why Consensus?

You are about to build a key-value store that survives machine failures. Before writing a line of Raft, be precise about the problem it solves — every Raft rule you will implement is a direct answer to one of the disasters below.

How the obvious designs lose data

One server. SET balance 100 lands on a single box. The box dies: your data is unavailable, possibly gone. No agreement problem — and no fault tolerance.

Primary + async backup. The primary acknowledges SET balance 100, then crashes before the backup received it. Ops promotes the backup, which serves the OLD balance. You acked a write and then lost it: the lost-write failure.

Automatic failover. Worse: the primary was not dead — just cut off from the health checker. The backup gets promoted while the old primary is still alive and still accepting writes from the clients that can reach it. Two nodes each believe they are authoritative; their histories diverge; when the network heals there is no principled merge. That is split-brain, the failure Raft is engineered to make impossible.

The root difficulty: in an asynchronous network you cannot tell slow from dead. The FLP result (Fischer–Lynch–Paterson, 1985) makes it formal: no deterministic protocol can guarantee consensus in an async system where even one process may crash. Raft lives with FLP by randomizing timeouts — safety is unconditional; liveness is (very) probabilistic.

What consensus buys you

A consensus protocol makes all non-faulty nodes agree on one ordered sequence of operations — a replicated log. Each node feeds that log, in order, into a deterministic state machine (for us: a KV map). Same log, same order, deterministic apply ⇒ identical state everywhere. A cluster of 2f+1 nodes tolerates f crashed nodes without losing data or availability.

The family tree

• Paxos (Lamport; written ~1989, published 1998): the original. Provably correct, famously hard to implement whole. Google's Chubby, Spanner, Megastore.
• Multi-Paxos: Paxos plus a stable leader, so you skip a full voting round per operation — conceptually where Raft lands too.
• Viewstamped Replication (Oki & Liskov, 1988): the same ideas, earlier.
• Zab: ZooKeeper's atomic broadcast; predates Raft.
• Raft (Ongaro & Ousterhout, 2014): engineered for understandability. Runs etcd, Consul, CockroachDB, TiKV — and Kubernetes keeps its entire control-plane state in etcd.
• Byzantine protocols (PBFT, HotStuff): tolerate malicious nodes; the tool for mutually untrusting parties — blockchains, multi-org ledgers.
• Gossip is not consensus. Epidemic protocols spread membership and metadata across thousands of nodes cheaply, but nobody agrees on a single order of operations. Different job.

Sometimes the answer is no consensus at all: a single-node app, or a primary with read replicas that never promises safe automatic failover, performs no agreement.

Your exercise

Classify each input line as RAFT, PAXOS, BFT, GOSSIP, or NONE — one output line per input line, and the grader does send several lines at once (3-node etcd cluster followed by A single-node application must print RAFT then NONE). Match against the whole line, not the first word. The grader-caught mistake is keyword reflex: Single-node Redis instance must print NONE — "single-node" means there is nothing to agree on, whatever database is named. Likewise Cassandra-like ring membership of 1000 nodes via gossip is GOSSIP (dissemination, not agreement), and Google Chubby lock service is PAXOS.