Distributed Consensus
Distributed consensus is the problem of getting multiple nodes in a network to agree on a value despite failures and message delays. Algorithms like Paxos and Raft solve this to enable replicated state machines, leader election, and consistent configuration in distributed systems.
itDistributed systems, messaging, and integration | OpenSkills.info
Intro
Distributed Consensus
Distributed consensus lets separate processes choose one durable result even when messages are delayed and some processes fail. It is the coordination core behind replicated state machines, metadata services, leader election, and strongly consistent storage.
The hard part is not collecting votes on a healthy network. The hard part is preserving one decision when failures hide which processes are alive and which messages will arrive later.
The problem consensus solves
Imagine three replicas that maintain the same key-value store. A client asks to set mode to safe. Every replica must apply that command in the same log position. If another replica applies mode to fast in that position, the copies no longer represent one service.
A consensus protocol controls which value or log entry becomes chosen. A useful specification separates three goals:
- Agreement: correct participants do not decide different values.
- Validity: the decided value satisfies the protocol's proposal rules.
- Termination: correct participants eventually decide under the stated timing and failure assumptions.
Agreement and validity are safety properties. A safety violation produces a wrong result. Termination is a liveness property. A liveness failure leaves the system waiting.
This distinction explains why a minority partition usually stops accepting writes. Refusing work hurts availability, but inventing a second committed history would break safety.
From one decision to a replicated service
Continue the course
This section is part of the paid course.
See pricing to subscribe, or log in if you already have access.
Where this skill leads
Relevant careers
See how this topic contributes to broader role-level skill maps.
Sources
- https://raft.github.io/index.html
Supports
- Consensus as agreement on values among servers
- Replicated state machine purpose and majority availability examples
- Official access to the Raft paper, dissertation, specification, and visualizations
- https://raft.github.io/raft.pdf
Supports
- Replicated state machines and ordered command logs
- Raft server states, terms, elections, randomized timeouts, and heartbeats
- Log replication, conflict repair, commitment, safety, and client interaction
- Majority failure tolerance, membership changes, and log compaction
- Comparison of Raft with Multi-Paxos and other consensus algorithms
- https://raft.github.io/raftscope/index.html
Supports
- Interactive observation of a five-server Raft cluster
- Elections, terms, replicated logs, partitions, and recovery behavior
- https://www.microsoft.com/en-us/research/publication/2016/12/paxos-simple-Copy.pdf
Supports
- Proposers, acceptors, learners, numbered proposals, promises, and accepted values
- Majority quorum intersection and the conditions that preserve one chosen value
- Extending single-value Paxos toward a sequence of state-machine commands
- https://www.microsoft.com/en-us/research/publication/paxos-made-simple/
Supports
- Authoritative publication metadata and access point for Paxos Made Simple
- Lamport's stated purpose and scope for the paper
- https://www.microsoft.com/en-us/research/publication/the-abcds-of-paxos/
Supports
- Consensus as a basis for replicated state machines
- Abstract Paxos roles and comparison of crash and Byzantine versions
- Safety, liveness, and performance as separate protocol concerns
- https://groups.csail.mit.edu/tds/papers/Lynch/pods83-flp-scanned.pdf
Supports
- Agreement, validity, and eventual decision requirements
- Impossibility of guaranteed deterministic consensus termination in complete asynchrony with one possible crash
- Indistinguishability of delayed communication and process failure
- Transaction commit as a motivating agreement problem
- https://groups.csail.mit.edu/tds/papers/Lynch/jacm88.pdf
Supports
- Synchronous, asynchronous, and partially synchronous timing models
- Unknown bounds and bounds that hold after an unknown stabilization time
- Fault-tolerant consensus progress under partial synchrony
- https://www.usenix.org/conference/osdi-99/presentation/practical-byzantine-fault-tolerance
Supports
- Byzantine faults as arbitrary behavior caused by attacks or software errors
- Practical Byzantine fault-tolerant state-machine replication
- Distinction between Byzantine and narrower crash-fault assumptions
- https://www.microsoft.com/en-us/research/publication/consensus-on-transaction-commit/
Supports
- Relationship between consensus and distributed transaction commit
- Two-phase commit as a zero-fault-tolerant form of Paxos Commit
- Paxos Commit's use of separate consensus decisions for participants
- Blocking and fault-tolerance differences between two-phase commit and Paxos Commit