EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Psym: Efficient Symbolic Exploration of Distributed Systems

Lauren Pick, Ankush Desai, Aarti Gupta

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →