Linearizability
The correctness condition for concurrent objects, and how it differs from serializability (Conflict serializability and two-phase locking) and sequential...
Distributed-Systems
Consistent Hashing
Adding a node should move 1/n of the keys, not all of them. One idea, and virtual nodes to fix its variance (Balls into bins and the power of two choices).
The CALM Theorem and CRDTs
A program can be coordination-free iff it's monotone. The positive result hiding behind all the impossibility ones.
The CAP Theorem and PACELC
What it actually says, why it's routinely misquoted, and why latency (the "ELC") is the part that governs real designs.
Paxos, Raft, and the Shape of Consensus
How real systems dodge FLP impossibility: safety always, liveness only when the network cooperates.
Quorum Intersection (R + W > N)
One inequality generating the entire read/write consistency tradeoff space.
The Byzantine Generals Problem
You need 3f+1 nodes to tolerate f liars, and that bound is tight.
FLP Impossibility
No deterministic consensus in an asynchronous system with one crash fault. The rigorous theorem that CAP only gestures at.
Vector Clocks and Causal Consistency
Detecting concurrency exactly, at the cost of O(n) metadata. The tradeoff every eventually-consistent store makes.
Happens-Before and Lamport Clocks
There is no global "now"; causality is the only ordering you get. The foundational conceptual shift of the whole part.
Balls Into Bins and the Power of Two Choices
Random placement gives max load ~log n / log log n; picking the emptier of two random bins collapses it to log log n.
The Two Generals Problem
Agreement over a lossy channel is impossible. Why exactly-once delivery is a lie and idempotency is the real answer.
Gustafson's Law and the Universal Scalability Law
Amdahl's rebuttal, and then the law that adds a negative term for coordination: past a point, more nodes make it slower.