Approximate Distributed Monitoring under Partial Synchrony: Balancing Speed and Accuracy
Preprint
Abstract
In distributed systems with processes that do not share a global clock, \emph{partial synchrony} is achieved by clock synchronization that guarantees bounded clock skew among all applications. Existing solutions for distributed runtime verification under partial synchrony against temporal logic specifications are exact but suffer from significant computational overhead. In this paper, we propose an \emph{approximate} distributed monitoring algorithm for Signal Temporal Logic (STL) that mitigates this issue by abstracting away potential interleaving behaviors. This conservative abstraction enables a significant speedup of the distributed monitors, albeit with a tradeoff in accuracy. We address this tradeoff with a methodology that combines our approximate monitor with its exact counterpart, resulting in enhanced efficiency without sacrificing precision. We evaluate our approach with multiple experiments, showcasing its efficacy in both real-world applications and synthetic examples.Keywords
All Related Versions
This publication has 12 references indexed in Scilit:
- Quantitative Safety and Liveness2023
- Decentralized Asynchronous Crash-resilient Runtime VerificationJournal of the ACM, 2022
- Abstract Monitors for Quantitative Specifications2022
- Quantitative and Approximate Monitoring2021
- Organising LTL monitors over distributed systems with a global clockFormal Methods in System Design, 2016
- Decentralised LTL monitoringFormal Methods in System Design, 2016
- Monitoring properties of analog and mixed-signal circuitsInternational Journal on Software Tools for Technology Transfer, 2012
- Runtime Verification with State Estimation2012
- Z3: An Efficient SMT Solver2008
- Techniques and applications of computation slicingDistributed Computing, 2005