Distributed causal memory: modular specification and verification in higher-order distributed separation logic
Open Access
- 4 January 2021
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Programming Languages
- Vol. 5 (POPL) , 1-29
Abstract
We present the first specification and verification of an implementation of a causally-consistent distributed database that supports modular verification of full functional correctness properties of clients and servers. We specify and reason about the causally-consistent distributed database in Aneris, a higher-order distributed separation logic for an ML-like programming language with network primitives for programming distributed systems. We demonstrate that our specifications are useful, by proving the correctness of small, but tricky, synthetic examples involving causal dependency and by verifying a session manager library implemented on top of the distributed database. We use Aneris's facilities for modular specification and verification to obtain a highly modular development, where each component is verified in isolation, relying only on the specifications (not the implementations) of other components. We have used the Coq formalization of the Aneris logic to formalize all the results presented in the paper in the Coq proof assistant.Keywords
Funding Information
- Villum Fonden (25804)
This publication has 42 references indexed in Scilit:
- You don't know jack about shared variables or memory modelsCommunications of the ACM, 2012
- An Axiomatic Memory Model for POWER Multiprocessors2012
- Eventually Consistent Transactions2012
- Concurrent Abstract Predicates2010
- Dafny: An Automatic Program Verifier for Functional Correctness2010
- BigtableACM Transactions on Computer Systems, 2008
- Brewer's conjecture and the feasibility of consistent, available, partition-tolerant web servicesACM SIGACT News, 2002
- The model checker SPINIEEE Transactions on Software Engineering, 1997
- Causal memory: definitions, implementation, and programmingDistributed Computing, 1995
- Hybrid systems in TLA+1993