Consensus

Fischer, Lynch, Paterson 1985 · Lamport 1998 · Wikipedia

The consensus problem: get all non-faulty nodes to agree on a single value. The FLP impossibility result says no deterministic algorithm can guarantee consensus in an asynchronous system if even one node can crash. Paxos solves it anyway by being non-deterministic (it may not terminate, but if it does, it is correct).

The consensus problem

Each node proposes a value. All non-faulty nodes must decide the same value (agreement). The decided value must have been proposed by some node (validity). Each node decides at most once (termination, in practice). These three properties are deceptively simple. Getting all three with crash failures is the core challenge.

Scheme

; Consensus: all nodes agree on one proposed value.
; Three properties:
;   1. Agreement: all decide the same value
;   2. Validity: decided value was proposed
;   3. Termination: eventually everyone decides

(define proposals (list "A" "B" "A"))

; Naive approach: pick the majority
(define (count-votes val proposals)
  (length (filter (lambda (p) (equal? p val)) proposals)))

(define (majority-vote proposals)
  (let ((a-count (count-votes "A" proposals))
        (b-count (count-votes "B" proposals)))
    (if (> a-count b-count) "A" "B")))

(display "Proposals: ") (display proposals) (newline)
(display "Majority vote: ") (display (majority-vote proposals)) (newline)
; Works when everyone can see all proposals.
; Breaks when messages are lost or delayed.
(display "Problem: what if node 3 crashes before sending?")

FLP impossibility

Fischer, Lynch, and Paterson proved in 1985 that no deterministic consensus protocol can guarantee both safety (agreement + validity) and liveness (termination) in an asynchronous system where even one process can crash. The proof constructs an execution where the algorithm is always one step away from deciding but never does. This is not a practical obstacle. It means you need randomization, timeouts, or partial synchrony assumptions.

Paxos overview

Paxos uses two phases. Phase 1 (prepare): the proposer picks a number n, sends prepare(n) to acceptors. Acceptors promise not to accept anything below n and return any value they already accepted. Phase 2 (accept): the proposer sends accept(n, v) where v is the highest-numbered previously accepted value, or its own if none. Acceptors accept if they have not promised a higher number. A value is chosen when a majority of acceptors accept the same proposal.

Scheme

; Simplified Paxos: two phases with three acceptors.
; Phase 1: prepare(n) -> promise or reject
; Phase 2: accept(n, v) -> accepted or reject

; Acceptor state: highest promise, accepted (n, v)
(define promises (list 0 0 0))
(define accepted-n (list 0 0 0))
(define accepted-v (list #f #f #f))

(define (list-set lst i val)
  (let loop ((l lst) (j 0) (acc (list)))
    (if (null? l) (reverse acc)
        (loop (cdr l) (+ j 1)
              (cons (if (= j i) val (car l)) acc)))))

(define (prepare proposal-n acceptor-id)
  (if (> proposal-n (list-ref promises acceptor-id))
      (begin
        (set! promises (list-set promises acceptor-id proposal-n))
        (display "  Acceptor ") (display acceptor-id)
        (display " promises n=") (display proposal-n) (newline)
        #t)
      #f))

(define (accept proposal-n value acceptor-id)
  (if (>= proposal-n (list-ref promises acceptor-id))
      (begin
        (set! accepted-n (list-set accepted-n acceptor-id proposal-n))
        (set! accepted-v (list-set accepted-v acceptor-id value))
        (display "  Acceptor ") (display acceptor-id)
        (display " accepts (") (display proposal-n)
        (display ", ") (display value) (display ")") (newline)
        #t)
      #f))

(display "Phase 1: prepare(1)") (newline)
(prepare 1 0) (prepare 1 1) (prepare 1 2)

(display "Phase 2: accept(1, 'X')") (newline)
(accept 1 "X" 0) (accept 1 "X" 1)
; Majority (2 of 3) accepted -> value X is chosen
(display "Value 'X' chosen by majority.")

; Simplified Paxos: two phases with three acceptors.
; Phase 1: prepare(n) -> promise or reject
; Phase 2: accept(n, v) -> accepted or reject

; Acceptor state: highest promise, accepted (n, v)
(define promises (list 0 0 0))
(define accepted-n (list 0 0 0))
(define accepted-v (list #f #f #f))

(define (list-set lst i val)
  (let loop ((l lst) (j 0) (acc (list)))
    (if (null? l) (reverse acc)
        (loop (cdr l) (+ j 1)
              (cons (if (= j i) val (car l)) acc)))))

(define (prepare proposal-n acceptor-id)
  (if (> proposal-n (list-ref promises acceptor-id))
      (begin
        (set! promises (list-set promises acceptor-id proposal-n))
        (display "  Acceptor ") (display acceptor-id)
        (display " promises n=") (display proposal-n) (newline)
        #t)
      #f))

(define (accept proposal-n value acceptor-id)
  (if (>= proposal-n (list-ref promises acceptor-id))
      (begin
        (set! accepted-n (list-set accepted-n acceptor-id proposal-n))
        (set! accepted-v (list-set accepted-v acceptor-id value))
        (display "  Acceptor ") (display acceptor-id)
        (display " accepts (") (display proposal-n)
        (display ", ") (display value) (display ")") (newline)
        #t)
      #f))

(display "Phase 1: prepare(1)") (newline)
(prepare 1 0) (prepare 1 1) (prepare 1 2)

(display "Phase 2: accept(1, 'X')") (newline)
(accept 1 "X" 0) (accept 1 "X" 1)
; Majority (2 of 3) accepted -> value X is chosen
(display "Value 'X' chosen by majority.")

Neighbors

Cross-references

🔑 Logic Ch.1 — arguments: consensus is distributed agreement, requiring valid reasoning under uncertainty
🌐 Ch.5 Raft — a more understandable consensus algorithm

← Replication by june.kim Raft →