Psym: Efficient Symbolic Exploration of Distributed Systems
Proceedings of the ACM on Programming Languages · 06.06.2023 · 7 (PLDI) · 660-685
DOI: 10.1145/3591247 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the ACM on Programming Languages, online erschienen am 06.06.2023. Verfasst von Lauren Pick und 2 weiteren Autor:innen. Die Arbeit wurde bisher 2-mal zitiert (Crossref) und nennt 92 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: National Science Foundation.
Abstract (Originalsprache)
Verification of distributed systems using systematic exploration is daunting because of the many possible interleavings of messages and failures. When faced with this scalability challenge, existing approaches have traditionally mitigated state space explosion by avoiding exploration of redundant states (e.g., via state hashing) and redundant interleavings of transitions (e.g., via partial-order reductions). In this paper, we present an efficient symbolic exploration method that not only avoids redundancies in states and interleavings, but additionally avoids redundant computations that are performed during updates to states on transitions. Our symbolic explorer leverages a novel, fine-grained, canonical representation of distributed system configurations (states) to identify opportunities for avoiding such redundancies on-the-fly. The explorer also includes an interface that is compatible with abstractions for state-space reduction and with partial-order and other reductions for avoiding redundant interleavings. We implement our approach in the tool Psym and empirically demonstrate that it outperforms a state-of-the-art exploration tool, can successfully verify many common distributed protocols, and can scale to multiple real-world industrial case studies across
Förderung
- National Science Foundation
Zitieren
APA
Pick, L., Desai, A., & Gupta, A. (2023). Psym: Efficient Symbolic Exploration of Distributed Systems. Proceedings of the ACM on Programming Languages, 7(PLDI), 660-685. https://doi.org/10.1145/3591247
Vancouver
Pick L, Desai A, Gupta A. Psym: Efficient Symbolic Exploration of Distributed Systems. Proceedings of the ACM on Programming Languages. 2023;7(PLDI):660-685. doi:10.1145/3591247
BibTeX
@article{Pick2023,
author = {Pick, Lauren and Desai, Ankush and Gupta, Aarti},
title = {Psym: Efficient Symbolic Exploration of Distributed Systems},
journal = {Proceedings of the ACM on Programming Languages},
year = {2023},
volume = {7},
number = {PLDI},
pages = {660--685},
doi = {10.1145/3591247}
}
EUVIMED