Distributed Systems and Fault Tolerance
Correctness Under Failure
Foundations
Distributed systems must reason about latency, message loss, partitions, crashes, and Byzantine behavior. A major challenge is that the system state is only partially observable and progress may be impossible under certain assumptions.
Key Terms
What is consensus in distributed computing?
Consensus is the canonical agreement problem in distributed computing.
Correct answer: Processes agree on one value despite failures
Why is fault tolerance central in distributed systems?
Robustness is necessary when failures are expected rather than exceptional.
Correct answer: Because nodes and communication links can fail, yet the system must still provide correct or useful service.
Failure Models
Crash fault model
- Nodes stop responding
- Simpler to handle
- Common in practical systems
Byzantine fault model
- Nodes may lie or behave arbitrarily
- Harder consensus problem
- Relevant for adversarial settings
Reasoning About a Distributed Protocol
-
1
Specify the failure model and network assumptions.
-
2
State safety properties, such as agreement or linearizability.
-
3
State liveness properties, such as termination or progress.
-
4
Prove invariants across message interleavings and failures.
-
5
Evaluate whether the protocol is practical under expected latency and fault rates.
Which property says a concurrent object appears to take effect atomically at some point between call and return?
Linearizability is the standard atomicity-like correctness condition for concurrent objects.
Correct answer: Linearizability
Design Trade-off
Stronger consistency usually costs more latency or reduced availability, so system design is often a deliberate compromise.
Research Frontier
Current research includes Byzantine fault tolerance, reconfigurable consensus, geo-distributed databases, and verified distributed protocols. Formal methods increasingly complement empirical evaluation.