Distributed Systems, Consensus, and Fault Tolerance
Consensus Under Adversity
Problem Setting
Distributed systems coordinate multiple processes or nodes that may fail, delay messages, or behave maliciously. The foundational challenge is achieving safety and liveness simultaneously despite uncertainty, partial synchrony, and adversarial conditions.
Key Terms
Impossibility and Assumptions
Many distributed guarantees are impossible without assumptions about timing, failure rate, or randomness; a rigorous protocol always states its model explicitly.
Fault Models
Crash faults
- Nodes stop responding
- Simpler to tolerate than arbitrary behavior
Byzantine faults
- Nodes may lie, equivocate, or collude
- Requires stronger assumptions and more communication
What does the FLP result show in the classical asynchronous model?
FLP proves deterministic consensus is impossible in a fully asynchronous system with one possible fault.
Correct answer: Deterministic consensus cannot be guaranteed with even one possible crash fault
Name one technique used to circumvent classical consensus impossibility results.
Randomized protocols can achieve probabilistic termination where deterministic ones cannot in the same model.
Correct answer: Randomization
Consistency Models
Research in distributed databases and replicated state machines studies strong consistency, eventual consistency, linearizability, and causal ordering. Each model trades off latency, availability, and implementation complexity.
Which trade-off is most closely associated with the CAP theorem?
CAP concerns the simultaneous presence of consistency, availability, and partition tolerance under network partitioning.
Correct answer: Consistency, Availability, and Partition tolerance
Why are explicit system models essential in distributed algorithms research?
Without a precise model, safety and liveness claims are not meaningful.
Correct answer: Because guarantees depend critically on assumptions about timing, failures, and communication