Скачать или смотреть [PLDI'23] Performal: Formal Verification of Latency Properties for Distributed Systems

Performal: Formal Verification of Latency Properties for Distributed Systems (Video, PLDI 2023)
Tony Nuda Zhang, Upamanyu Sharma, and Manos Kapritsos
(University of Michigan, USA; Massachusetts Institute of Technology, USA; University of Michigan, USA)

Abstract: Understanding and debugging the performance of distributed systems is a notoriously hard task, but a critical one. Traditional techniques like logging, tracing, and benchmarking represent a best-effort way to find performance bugs, but they either require a full deployment to be effective or can only find bugs after they manifest. Even with such techniques in place, real deployments often exhibit performance bugs that cause unwanted behavior.


In this paper, we present Performal, a novel methodology that leverages the recent advances in formal verification to provide rigorous latency guarantees for real, complex distributed systems. The task is not an easy one: it requires carefully decoupling the formal proofs from the execution environment, formally defining latency properties, and proving them on real, distributed implementations. We used Performal to prove rigorous upper bounds for the latency of three applications: a distributed lock, ZooKeeper and a MultiPaxos-based State Machine Replication system. Our experimental evaluation shows that these bounds are a good proxy for the behavior of the deployed system and can be used to identify performance bugs in real-world systems.

Article: https://doi.org/10.1145/3591235

Supplementary archive: https://doi.org/10.5281/zenodo.7812534 (Badges: Artifacts Available, Artifacts Evaluated — Reusable)

ORCID: https://orcid.org/0009-0009-0288-8270, https://orcid.org/0000-0002-5446-3284, https://orcid.org/0000-0002-4368-7418

Video Tags: distributed systems, systems verification, latency, performance, pldi23main-p102-p, doi:10.1145/3591235, doi:10.5281/zenodo.7812534, orcid:0009-0009-0288-8270, orcid:0000-0002-5446-3284, orcid:0000-0002-4368-7418, Artifacts Available, Artifacts Evaluated — Reusable

Presentation at the PLDI 2023 conference, June 17–21, 2023, https://pldi23.sigplan.org/
Sponsored by ACM SIGPLAN,