Paper Info
Title
Much ADO about failures: a fault-aware model for compositional verification of strongly consistent distributed systems
Abstract
AbstractDespite recent advances, guaranteeing the correctness of large-scale distributed applications without compromising performance remains a challenging problem. Network and node failures are inevitable and, for some applications, careful control over how they are handled is essential. Unfortunately, existing approaches either completely hide these failures behind an atomic state machine replication (SMR) interface, or expose all of the network-level details, sacrificing atomicity. We propose a novel, compositional, atomic distributed object (ADO) model for strongly consistent distributed systems that combines the best of both options. The object-oriented API abstracts over protocol-specific details and decouples high-level correctness reasoning from implementation choices. At the same time, it intentionally exposes an abstract view of certain key distributed failure cases, thus allowing for more fine-grained control over them than SMR-like models. We demonstrate that proving properties even of composite distributed systems can be straightforward with our Coq verification framework, Advert, thanks to the ADO model. We also show that a variety of common protocols including multi-Paxos and Chain Replication refine the ADO semantics, which allows one to freely choose among them for an application's implementation without modifying ADO-level correctness proofs.
Year
DOI
Venue
2021
10.1145/3485474
Proceedings of the ACM on Programming Languages
Keywords
DocType
Volume
distributed systems, formal verification, proof assistants, Coq
Journal
5
Issue
Citations 
PageRank 
OOPSLA
0
0.34
References 
Authors
0
4
Name
Order
Citations
PageRank
Wolf Honoré100.68
Jieung Kim2322.51
Ji-Yong Shin300.68
Zhong Shao489768.80