IronFleet
Authors:
Open Access
- 26 June 2017
- journal article
- Published by Association for Computing Machinery (ACM) in Communications of the ACM
- Vol. 60 (7) , 83-92
Abstract
Distributed systems are notorious for harboring subtle bugs. Verification can, in principle, eliminate these bugs, but it has historically been difficult to apply at full-program scale, much less distributed system scale. We describe a methodology for building practical and provably correct distributed systems based on a unique blend of temporal logic of actions-style state-machine refinement and Hoare-logic verification. We demonstrate the methodology on a complex implementation of a Paxos-based replicated state machine library and a lease-based sharded key-value store. We prove that each obeys a concise safety specification as well as desirable liveness requirements. Each implementation achieves performance competitive with a reference system. With our methodology and lessons learned, we aim to raise the standard for distributed systems from "tested" to "correct."Keywords
This publication has 22 references indexed in Scilit:
- Using lightweight modeling to understand chordACM SIGCOMM Computer Communication Review, 2012
- Verifying distributed systemsACM SIGPLAN Notices, 2009
- The Farsite projectACM SIGOPS Operating Systems Review, 2007
- Simplify: a theorem prover for program checkingJournal of the ACM, 2005
- Checking Cache-Coherence Protocols with TLA+Formal Methods in System Design, 2003
- The part-time parliamentACM Transactions on Computer Systems, 1998
- The temporal logic of actionsACM Transactions on Programming Languages and Systems, 1994
- Impossibility of distributed consensus with one faulty processJournal of the ACM, 1985
- An axiomatic basis for computer programmingCommunications of the ACM, 1969
- Assigning meanings to programs1967