Skip to content

CONCEPT Cited by 1 source

Consensus algorithm

A consensus algorithm allows a set of machines communicating over a network to agree on the same sequence of values (e.g., key-value store operations) as long as a majority remains alive and able to communicate.

Definition

A consensus algorithm provides two guarantees:

  1. Safety — if any two replicas decide on the value for a slot, those values are the same (no two up-to-date machines ever disagree about the world)
  2. Liveness — the system eventually makes progress (a value is eventually decided) as long as a majority of replicas can communicate

Fault tolerance model

Standard consensus algorithms tolerate f faults in a system of 2f+1 machines (crash-fault tolerance). They do not handle Byzantine faults (actively malicious actors).

Leader-based vs leaderless

  • Leader-based (e.g., Raft, Multi-Paxos): a single authoritative leader drives all writes; followers replicate. Simple to understand but creates a single point of temporary failure.
  • Leaderless (e.g., QuePaxa): any replica can drive consensus. A leader may exist for efficiency but is not required for progress. See concepts/leaderless-consensus.

The cost of consensus

All consensus algorithms require communication round-trips between the proposer and a majority of replicas. Latency is proportional to the network distance between those replicas — there is no getting around this fundamental cost.

Seen in

Last updated · 573 distilled / 1,747 read