Paxos Made Simple conceptpaper
Lamport, 2001.
Lamport, 2001. Lamport's response to widespread complaints that the original Paxos paper (1989, finally published 1998) was incomprehensible. Walks through the algorithm in plain prose. Still difficult, but the most-cited 'this is how Paxos actually works' reference. If you're going to read one Lamport paper on consensus, this is it — and even then, plan to read it multiple times.