Distributed Systems Theory

Consensus Algorithms

Consensus lets a cluster of unreliable, possibly-partitioned nodes agree on a single value — a leader, a log entry, a committed transaction — with a provable guarantee that a majority quorum tolerates the rest failing. Raft is the algorithm most systems actually implement; Paxos proved it was possible first.

Every decision needs agreement from a majority (quorum) of nodes — a minority can crash or partition away without breaking correctness
Raft splits the problem into three understandable pieces: leader election, log replication, and safety
A monotonically increasing term number acts as a logical clock — at most one leader per term, enforced by nodes rejecting stale-term messages
A log entry is only committed once replicated to a majority; only then does the leader apply it and reply to the client
Paxos proves consensus is possible with majority quorums; Raft is deliberately engineered so it's implementable without a PhD
Real systems rarely hand-roll this: etcd and Consul (Raft), ZooKeeper (Zab, a Paxos relative), and Kafka's KRaft controller all lean on a battle-tested implementation

A single node deciding something is trivial; the hard part is a cluster of nodes — any of which can crash, with network links that can partition — agreeing on one value without ever disagreeing about what was decided. Consensus algorithms solve exactly this, and they sit under almost every strongly-consistent distributed system: replicated logs, leader election, distributed locks, configuration stores.

Raft: leader election

Every node is a follower, candidate, or leader. Followers expect periodic heartbeats from a leader; if a randomized election timeout (typically 150-300ms, randomized to avoid tied elections) elapses with none, a follower becomes a candidate, increments its term, votes for itself, and requests votes from the rest of the cluster. Whichever candidate secures a majority becomes leader for that term.

Raft leader election

A candidate that wins a majority of votes becomes leader for that term

Simplified RequestVote handling

boolean handleRequestVote(long candidateTerm, String candidateId, long candidateLastLogIndex) {
    if (candidateTerm < currentTerm) return false;              // stale candidate
    if (candidateTerm > currentTerm) {
        currentTerm = candidateTerm;
        votedFor = null;                                          // new term, vote resets
    }
    boolean logIsUpToDate = candidateLastLogIndex >= myLastLogIndex();
    if ((votedFor == null || votedFor.equals(candidateId)) && logIsUpToDate) {
        votedFor = candidateId;
        return true;
    }
    return false;
}

Safety: why a committed entry never disappears

The leader appends new entries to its log and replicates them to followers; once a majority has the entry, the leader marks it committed. Because any future leader must also win votes from a majority, and any two majorities overlap in at least one node, a future leader is guaranteed to have seen every previously committed entry — it cannot win an election without it. This majority-overlap property is the same idea Quorum Systems generalizes to ordinary reads and writes.

Paxos vs Raft
	Paxos	Raft
Goal	Prove consensus is achievable with majority quorums	Make consensus implementable and debuggable
Structure	Single decree, extended awkwardly to logs (Multi-Paxos)	Purpose-built for replicated logs from the start
Leader	Implicit, re-derived per instance, hard to reason about	Explicit, elected, holds the log until it fails
Used by	Chubby, Spanner (variants)	etcd, Consul, CockroachDB, Kafka (KRaft)