Deconstructing Paxos

The Paxos part-time parliament protocol of Lamport provides a non trivial but very practical way to implement fault-tolerant deterministic services over a distributed message passing system. This paper deconstructs Paxos and modularly reconstructs more resilient and efficient variants of it, which can furthermore be customised for specific system configurations. The deconstruction consists in factoring out the key algorithmic principles of Paxos within three abstractions: round-based register, round-based consensus, and weak leader election. Our modularisation helps better understand, improve and adapt the protocol. We show how to (1) alleviate the need for forced logs if some processes remain up for sufficiently long, (2) augment the resilience of the protocol against unstable processes, (3) enable single process decision with shared commodity disks, and (4) reduce the number of communication steps during stable periods of the system.