Consensus Protocols
Consensus Protocols are concrete protocol families that realize consensus under specified network, failure, timing, persistence, and membership assumptions.
Protocols such as Paxos, Multi-Paxos, Raft, Zab, and Viewstamped Replication use quorum intersection, terms or epochs, durable metadata, and recovery rules to make distributed participants agree on values or log positions. In practice they are most often used to build replicated logs, replicated state machines, leader election, membership changes, configuration stores, and strongly consistent storage partitions.
A consensus protocol usually provides:
- A proposal or command value to decide.
- A ballot, term, epoch, or view that orders competing leadership attempts.
- A quorum rule that prevents two incompatible decisions from both committing.
- A replicated log or sequence of consensus instances.
- A commit rule that determines when a value is durable enough to expose.
- Recovery behavior that preserves decided values across crashes, restarts, and leader changes.
Consensus protocols are a realization choice, not a domain concept. They can support linearizability, strict serializability, and coherent replicated state, but only at the boundary they actually govern. Read routing, follower reads, caches, projections, asynchronous replication, membership changes, and clock or lease assumptions can weaken the guarantee exposed to observers.
The cost is coordination. Consensus protocols preserve a chosen order by requiring communication, durable metadata, quorum participation, and failure detection or timing assumptions. This can increase latency, reduce availability during partitions, and create operational coupling, but it lets systems construct distributed behavior that can be reasoned about using a sequential specification.
Operationally, consensus protocols tend to preserve safety even when progress is temporarily impossible. Their liveness depends on enough participants, storage, network behavior, and timing assumptions becoming available again.
External References
- Leslie Lamport, Paxos Made Simple, ACM SIGACT News, 32(4):51-58, December 2001.
- Diego Ongaro and John Ousterhout, In Search of an Understandable Consensus Algorithm, USENIX ATC, 2014.
- Barbara Liskov and James Cowling, Viewstamped Replication Revisited, MIT CSAIL, 2012.
Related concepts: consensus, safety and liveness, CAP theorem, coordination, consistency models, ordering, time, version, persistence, recovery, storage systems, infrastructure, network, brokers, actor systems.