What You Can Do By The End

• Define consensus and its properties
• Explain majority quorums
• Describe Raft elections and logs
• State the Byzantine generals problem
• Choose crash-tolerant or Byzantine-tolerant designs

Why Agreement Is Hard

• Machines crash and messages arrive late
• Two machines may decide different things
• Everyone must still settle on one answer
• Examples: who holds the lock, which payment came first

Three Properties Of Consensus

• Agreement: no two machines decide differently
• Validity: the decided value was proposed by someone
• Termination: every working machine decides
• Safety is never negotiable, liveness needs a calm network

The FLP Limit

• Fischer, Lynch and Paterson, 1985
• In a fully asynchronous network, one crash can block termination
• Real protocols use timeouts
• They keep safety and sometimes pause liveness

Replicated State Machines

• Servers run the same deterministic program
• Consensus fixes one order of commands
• Same commands in the same order gives the same state
• A returning server catches up by reading the log

log:  [1: set x=5] [2: add x,2] [3: set y=1]
A:    x=7, y=1
B:    x=7, y=1
C:    x=7, y=1

Majority Quorums

• A quorum is any majority of the machines
• Any two majorities share at least one machine
• That shared machine remembers the earlier decision
• Five machines: any two groups of three overlap

machines: A B C D E
group 1:  A B C
group 2:  C D E
overlap:  C

How Many Machines Do You Need?

• To survive f crashes, use at least 2f+1 machines
• Five machines survive two crashes
• Four survive only one, same as three
• A minority partition cannot decide

for n in range(3, 8):
    f = (n - 1) // 2
    print(n, 'machines survive', f, 'crashes')

Paxos: The Original

• Designed in the late 1980s, published in 1998
• Phase 1: proposer asks a majority to promise
• Phase 2: proposer asks them to accept a value
• Earlier accepted values must be carried forward

Raft: Three Roles

• Follower: listens to the leader
• Candidate: asks for votes after a timeout
• Leader: sends heartbeats and handles clients
• A term number counts elections

follower --timeout--> candidate
candidate --majority--> leader
leader --sees higher term--> follower

Raft: Replicating The Log

• Client sends a command to the leader
• Leader appends it and tells the followers
• A majority stored it: the entry is committed
• A new leader must hold every committed entry

Byzantine Generals

• Generals must attack together or retreat together
• Messengers carry the orders
• Some generals may be traitors
• Traitors tell different generals different things

The 3F+1 Rule

• To tolerate f traitors, you need at least 3f+1 generals
• Three generals cannot handle one traitor
• Four can
• Crash tolerance needs only 2f+1

for f in range(1, 5):
    print('tolerate', f, 'liars: need', 3 * f + 1, 'machines')

Byzantine Fault Tolerant Protocols

• PBFT (Castro and Liskov, 1999) made BFT practical
• Replicas act after agreement from 2f+1 of 3f+1
• Messages grow with the square of group size
• Bitcoin uses proof of work for open membership

Choosing A Design

• One owner, crash faults: Raft
• Several owners who distrust each other: BFT
• Anyone may join: protocols for open membership
• Remember the latency floor from week 2

Recap

• Consensus needs agreement, validity and termination
• Majorities overlap and prevent conflicts
• Raft elects a leader and replicates a log
• Byzantine faults need 3f+1 machines

Next Week

• Decentralized storage and content addressing
• IPFS, Filecoin and Arweave
• Git as a Merkle DAG

Questions And Exercise

• Run quorum.py and read the table
• Explore the Raft visualization
• Explain why four servers equal three for crashes