Consistency
- Two phase commit (M. Kleppman): https://www.youtube.com/watch?v=-_rdWB9hN1c
- https://css.csail.mit.edu/6.824/2014/schedule.html
- Paxos made Simple by Leslie Lamport: https://css.csail.mit.edu/6.824/2014/papers/paxos-simple.pdf
Atomic commitment problem
- In the context of ACID:
- Atomicity: A transaction either commits or aborts
- Consistency relies on Atomicity
- In Distributed Systems:
- If the transaction updates data on multiple nodes, this implies:
- Either all nodes must commit, or all must abort
- If any node crashes, all must abort
- If the transaction updates data on multiple nodes, this implies:
Consensus vs Atomic commit
| Consensus | Atomic commit |
|---|---|
| One or more nodes propose a value | Every node votes whether to commit or abort |
| Any one of the proposed values is decided | Must commit if all nodes vote to commit; must abort if ≥ 1 nodes vote to abort |
| Crashed nodes can be tolerated, as long as a quorum is working | Must abort if a participating node crashes |
Two Phase commit (2PC)
- Algorithm to achieve Atomic commit
Linearizability
- aka Atomic consistency, strong consistency, immediate consistency or external consistency