Consensus Algorithms: Raft and Paxos

Day 005: Consensus Algorithms: Raft and Paxos

Consensus is expensive because the system is buying one shared decision in a world where nodes can fail and messages can lag.

Today's "Aha!" Moment

The insight: Consensus is not "distributed voting." It is the mechanism a system uses when it must preserve one agreed decision or one ordered history despite crashes, delays, and uncertainty.

Why this matters: Many systems do not need consensus, but the ones that do cannot fake it. If the system must ensure one leader, one metadata history, or one ordered set of committed operations, gossip and retries are not enough.

Concrete anchor: Picture a three- or five-node metadata cluster for a platform control plane. If two nodes disagree about who the leader is, the platform can start making contradictory decisions immediately.

The universal pattern: Uncertain communication + required agreement -> quorum-based coordination.

How to recognize when this applies:

Common misconceptions:

Real-world examples:

  1. Kubernetes metadata: The control plane needs one authoritative cluster state.
  2. Leader election: Two active leaders can corrupt ownership and ordering guarantees.
  3. Distributed databases: Metadata and commit ordering often require stronger coordination than ordinary background dissemination.
  4. Configuration stores: A system-wide configuration source must not split into competing truths during failure.

Why This Matters

The problem: Some distributed systems need one agreed result even when individual nodes fail or disagree temporarily about what is happening.

Before:

After:

Real-world impact: Consensus underlies metadata stores, control planes, configuration systems, and strongly coordinated databases across modern infrastructure.

Learning Objectives

By the end of this session, you will be able to:

  1. Explain the consensus problem - Describe why some systems require one agreed decision or ordered history.
  2. Recognize the shared structure behind Raft and Paxos - Identify leadership, quorums, and quorum overlap as the main safety ideas across both families.
  3. Distinguish consensus from looser coordination - Explain when gossip or eventual convergence is not enough.

Core Concepts Explained

Concept 1: Consensus Exists to Protect Shared Invariants

Intuition: Consensus is the process by which a distributed system gets enough nodes to agree on a value or sequence of values so that the system can act as one coherent authority.

Practical implications: Without this, two parts of the system may both think they are correct leaders or both believe conflicting updates are committed.

Technical structure (how it works): Nodes exchange messages according to a protocol that requires a majority or quorum to accept certain transitions. The system prefers blocking or electing anew over allowing two incompatible histories to become committed truths.

Mental model: A committee can survive one absent member, but it still needs a rule for when a decision becomes official.

Concrete example / mini-scenario: A small control-plane cluster stores cluster membership and scheduling metadata. If two nodes both believe they are the leader after a failure, operators do not get "eventual truth"; they get conflicting writes.

When to use it:

Fundamental trade-off: [Specify what you gain, what you pay, and why this design is still worth it in context.]

Concept 2: Raft and Paxos Express the Same Safety Idea Differently

Intuition: Raft presents consensus as a leader managing an ordered replicated log. Paxos presents the same safety problem more abstractly through numbered proposals and quorum agreement.

Practical implications: Engineers often learn Raft operationally and treat Paxos as a separate mysterious topic. In practice, both are trying to prevent conflicting decisions by making later decisions respect what earlier quorums may already have accepted.

Technical structure (how it works): In Raft, followers wait for heartbeats, elect a leader when needed, and replicate the leader's log entries. In Paxos, proposers and acceptors exchange proposal numbers and values, and quorum overlap ensures that once a value is chosen, later rounds cannot safely choose a conflicting one.

Mental model: Raft is like one conductor keeping the score aligned. Paxos is like a committee whose voting rules force each new round to respect what a previous majority may already have decided.

Concrete example / mini-scenario: In that same metadata cluster, Raft explains the story as leader election plus log replication, while Paxos explains why any later quorum must respect values a previous quorum may already have accepted. The surface model changes, but the safety goal does not.

Code Example (If applicable):

def can_commit(acks, cluster_size):
    majority = (cluster_size // 2) + 1
    return acks >= majority

Note: The quorum rule looks simple, but it encodes the key safety idea behind both Raft and Paxos: two different majorities in the same cluster must overlap, which helps prevent conflicting committed histories.

When to use it:

Fundamental trade-off: [Specify what you gain, what you pay, and why this design is still worth it in context.]

Concept 3: Consensus Is a Trade-Off, Not a Free Upgrade

Intuition: Consensus buys stronger correctness, but it costs coordination rounds, quorum waits, and reduced availability for some operations during certain failures.

Practical implications: Engineers often overuse consensus because it sounds safer. In practice, it should be reserved for the system parts that truly require it.

Technical structure (how it works): The system waits for enough acknowledgments, handles leader failover, and may refuse progress during partitions that prevent a majority from forming. This is what preserves safety.

Mental model: Requiring multiple signatures makes a decision safer, but also slower and harder to complete when people are unreachable.

Concrete example / mini-scenario: If the metadata cluster loses majority during a partition, the safest behavior is often to stop accepting new committed writes rather than guess. That is the real price of preserving one official history.

When to use it:

Fundamental trade-off: [Specify what you gain, what you pay, and why this design is still worth it in context.]

Troubleshooting

Issue: Thinking consensus and replication are the same thing.

Why it happens / is confusing: Both involve multiple copies and communication among nodes.

Clarification / Fix: Replication is the act of distributing state. Consensus is the stronger rule set that decides when replicated state becomes officially agreed and ordered.

Issue: Assuming consensus should be used everywhere for safety.

Why it happens / is confusing: Strong agreement sounds universally better.

Clarification / Fix: Consensus is expensive. Use it where the invariant needs one shared truth, not where eventual spread or repair is enough.

Advanced Connections

Connection 1: Quorums <-> Shared Decision Safety

The parallel: Majority-based rules work because overlapping quorums reduce the risk of two incompatible truths both becoming official.

Real-world case: Leader election and committed log entries both rely on quorum overlap to preserve a coherent system history.

Connection 2: Consensus <-> Control Plane Design

The parallel: Consensus is often used for metadata and coordination state rather than for every user-facing data path.

Real-world case: Control planes, schedulers, and metadata services often need stronger guarantees than high-volume content delivery or background replication layers.

Resources

Optional Deepening Resources

Key Insights

  1. Consensus protects shared truth - It exists for cases where one agreed result or order is required.
  2. Raft and Paxos share the same safety backbone - They package consensus differently, but both rely on quorum overlap to keep conflicting histories from becoming official.
  3. Consensus is a costly tool - Use it where correctness requires it, not where looser convergence would already work.

Knowledge Check (Test Questions)

  1. When does a system most clearly need consensus?

    • A) When it needs one agreed leader or one ordered committed history.
    • B) When it only needs broad state dissemination over time.
    • C) When every node can make independent conflicting decisions safely.

  2. What do Raft and Paxos both rely on to keep conflicting decisions from both becoming official?

    • A) Overlapping majorities or quorums.
    • B) Perfectly synchronized clocks on every node.
    • C) One node broadcasting the answer to everyone else.

  3. Why is consensus not the default answer for every distributed problem?

    • A) Because it only works on a single machine.
    • B) Because it adds coordination cost and should be reserved for invariants that truly require shared agreement.
    • C) Because gossip already provides exactly the same guarantees.

Answers

1. A: Consensus is for protecting one shared decision or ordered history, such as leadership or metadata state.

2. A: Both protocol families rely on quorum overlap. If two quorums must share at least one node, the system has a way to carry forward previously accepted history instead of allowing two conflicting outcomes.

3. B: Consensus is valuable but expensive. Many system tasks only need propagation, repair, or eventual convergence rather than full agreement.

← Back to Learning