  Distributed consensus, the ability to reach agreement in the face of failures
and asynchrony, is a fundamental primitive for constructing reliable
distributed systems from unreliable components. The Paxos algorithm is
synonymous with distributed consensus, yet it performs poorly in practice and
is famously difficult to understand. In this paper, we re-examine the
foundations of distributed consensus. We derive an abstract solution to
consensus, which utilises immutable state for intuitive reasoning about safety.
We prove that our abstract solution generalises over Paxos as well as the Fast
Paxos and Flexible Paxos algorithms. The surprising result of this analysis is
a substantial weakening to the quorum requirements of these widely studied
algorithms.
