A distributed system is just a collection of independent computers that appear to its users as a single coherent system. The hardest part of building them isn't the computing: it's the coherence.
To act as a single system, the computers must agree on things. Who is the leader? What is the current value of x? Should we commit this transaction? Reaching this agreement over an unreliable network is known as the Consensus Problem.
To understand why consensus is so hard, we look at a famous thought experiment from 1975. Two generals, A and B, are camped on opposite hills. Between them in the valley is a city they want to attack.
They can only win if they attack at the exact same time. If one attacks alone, they die. They can only communicate by sending messengers through the valley, but the valley is dangerous: messengers might get captured.
Try to get both generals to a state of "SURE TO ATTACK". Send a message, then decide if you want to let the messenger through or "Capture" them to simulate network packet loss.
Did you figure it out? It is mathematically impossible for both generals to ever be 100% sure.
If General A sends "Attack at Dawn!", A doesn't know if the messenger made it. So A won't attack unless B sends an ACK (acknowledgment). But if B sends the ACK, B doesn't know if the ACK made it! If the ACK is lost, A won't attack, meaning B would attack alone and die. So B needs an ACK to their ACK. And A needs an ACK to the ACK of the ACK.
Because the network (the valley) is unreliable, deterministic consensus is impossible. This was formally proven in 1985 by the FLP Impossibility Theorem (Fischer, Lynch, Paterson), which states that in an asynchronous network where even one node might crash, no deterministic consensus algorithm can guarantee it will ever reach a conclusion.
If consensus is impossible, how do ZooKeeper, etcd, and CockroachDB work? They cheat.
We accept probabilistic consensus using timeouts. If a node doesn't hear an ACK within 500ms, it assumes the packet was dropped and retries. We also accept that we only need a Majority (Quorum) to agree, rather than every single node. We'll explore these mechanisms in the next lesson: Leader Election.