Interlude. The Machine That Agrees
illustrationFor many years I built systems where several servers have to store the same data and must never disagree. If one server thinks there are a hundred rubles in an account and another is sure there are fifty, the system is broken, even if both servers are working fine. Engineers have a boring name for this, state consistency, and a whole library of scientific papers on how to achieve it.
The most famous of them came out in 1982. Leslie Lamport, Robert Shostak and Marshall Pease described the problem of the Byzantine generals. Several generals have besieged a city, each with his own army, and they communicate only through messengers. The city can be taken if they all attack at once, but if only some of them attack, they will be slaughtered. Among the generals there are traitors who send opposite orders to different comrades, and messengers can be intercepted. The loyal generals need to agree on a single plan without knowing which of their comrades they can trust. The authors proved that the problem can be solved only if fewer than a third are traitors.
Lamport later devised a protocol by which servers reach agreement even if some of them drop out, and described it in a paper about a fictional parliament on the Greek island of Paxos, whose legislators keep wandering off from sessions on their own business. Lamport presented this talk dressed as an archaeologist in a hat like Indiana Jones’s, and the audience remembered the hat better than the algorithm. The reviewers didn’t appreciate the joke, the paper sat for almost ten years and came out only in 1998, and in 2013 Lamport received the Turing Award, the top prize in computer science. Today many distributed databases run on descendants of Paxos and on the simpler Raft algorithm, devised in 2014.
After sign-in
The rest of the book is for signed-in readers
Sign in with INITE or create an account. It takes a minute, and the book opens right here.