Module 6 - Distributed Systems

Consensus Algorithms

How distributed nodes agree on a single value despite failures.

1The Jury Deliberation Analogy

Simple Analogy

A jury must reach a unanimous verdict. Some jurors may be absent (crashed), notes may get lost (network issues), but they keep discussing until a majority agrees. That's consensus-reaching agreement despite failures.

Consensus is the process by which distributed nodes agree on a single value. Essential for replication, leader election, and distributed transactions.

2The Problem

FLP Impossibility

In an asynchronous system where even one process can crash, no deterministic consensus algorithm can guarantee termination.

Translation: Perfect consensus is theoretically impossible. Practical algorithms use timeouts and probability.

Safety

All nodes agree on the same value

Liveness

Eventually a decision is made

Fault Tolerance

Works despite some failures

3Paxos

Paxos (Leslie Lamport, 1989): The foundational consensus algorithm. Notoriously difficult to understand and implement correctly.

ProposerProposes values for consensus

AcceptorVotes on proposals, remembers accepted values

LearnerLearns the decided value

Basic Paxos Flow

Prepare

Proposer sends prepare(n) to acceptors with proposal number n

Promise

Acceptors respond with promise if n > any seen proposal

If majority promised, proposer sends accept(n, value)

Accepted

Acceptors accept if no higher proposal seen. Learners notified.

4Raft

Raft (2014): Designed to be understandable. Used in etcd, Consul, CockroachDB. Easier to implement correctly than Paxos.

Leader

Handles all client requests, replicates to followers

Follower

Passive, responds to leader/candidate requests

Candidate

Tries to become leader during election

Raft Key Concepts

TermMonotonically increasing election period. New term = new election.

Log ReplicationLeader appends entries to log, replicates to followers, commits when majority acknowledge.

Election TimeoutFollower becomes candidate if no heartbeat from leader.

5Comparison

Aspect	Paxos	Raft
Understandability	Difficult	Designed for clarity
Leader	Optional (Multi-Paxos)	Required (strong leader)
Log Ordering	Gaps possible	Contiguous
Used By	Google Chubby, Spanner	etcd, Consul, CockroachDB

6Key Takeaways

1Consensus = distributed nodes agreeing on a value

2Paxos: foundational but hard to understand

3Raft: easier, used in etcd, Consul, CockroachDB

4Requires majority quorum (N/2 + 1) for progress

5FLP impossibility: perfect consensus is theoretically impossible

?Quiz

1. 5-node Raft cluster. How many can fail and still make progress?

2. Why was Raft created?