CAP Theorem: ATM Simulation
The CAP theorem states that a distributed system can provide at most two of three guarantees simultaneously: Consistency, Availability, and Partition tolerance. Since network partitions are unavoidable in distributed systems, the practical choice is between consistency and availability during a partition.
This simulation uses a simple ATM network to illustrate the trade-off.
Scenario
Three ATMs are connected to a central bank backend. Each ATM can process withdrawals if it can verify the account balance with the backend. When a network partition isolates one ATM from the backend, the system must decide how to handle withdrawal requests at the disconnected ATM.
Simulation
Choice: Consistency (CP)
The isolated ATM rejects withdrawals until it can confirm the latest balance. The customer cannot withdraw money from this ATM, but the system guarantees that no overdraft or double-spend can occur.
Trade-off: The system sacrifices availability at the partitioned node to maintain a consistent view of the account balance across all nodes.
Real-world example: Some banking systems choose this approach to prevent overdrafts, accepting that customers at affected ATMs must wait or find another machine.
Choice: Availability (AP)
The isolated ATM allows withdrawals based on its last known balance. The customer can withdraw money, but the system may need reconciliation later if the balance was stale.
Trade-off: The system sacrifices consistency to remain available. The partitioned ATM may allow a withdrawal that, combined with withdrawals at other ATMs, exceeds the account balance.
Real-world example: Many ATM networks allow limited offline withdrawals (often with a cap) to keep the service available, accepting the small risk of overdrafts that can be reconciled later.
Key Takeaways
- The CAP theorem is not about choosing two of three properties in general — it is about what happens during a partition
- Network partitions are not a choice; they will happen in any distributed system
- The real decision is: when a partition occurs, do you prefer consistency or availability?
- Many real systems choose different strategies for different operations within the same system
- The trade-off is often a spectrum, not a binary choice — techniques like timeouts, quorums, and bounded staleness provide nuance
Further Reading
- Brewer's original conjecture (2000) and Gilbert & Lynch's proof (2002)
- The "CAP Twelve Years Later" article by Eric Brewer (2012) — clarifies common misconceptions
- PACELC theorem — extends CAP to consider latency vs. consistency even when there is no partition