Formal Verification of Multi-Paxos for Distributed Consensus
Authors:
Preprint
Abstract
This paper describes formal specification and verification of Lamport's Multi-Paxos algorithm for distributed consensus. The specification is written in TLA+, Lamport's Temporal Logic of Actions. The proof is written and checked using TLAPS, a proof system for TLA+. Building on Lamport, Merz, and Doligez's specification and proof for Basic Paxos, we aim to facilitate the understanding of Multi-Paxos and its proof by minimizing the difference from those for Basic Paxos, and to demonstrate a general way of proving other variants of Paxos and other sophisticated distributed algorithms. We also discuss our general strategies for proving properties about sets and tuples that helped the proof check succeed in significantly reduced time.Keywords
All Related Versions
This publication has 5 references indexed in Scilit:
- Paxos Made Moderately ComplexACM Computing Surveys, 2015
- The Heard-Of model: computing in distributed systems with benign faultsDistributed Computing, 2009
- Fast PaxosDistributed Computing, 2006
- Disk PaxosDistributed Computing, 2003
- The part-time parliamentACM Transactions on Computer Systems, 1998