Approximate Distributed Monitoring Under Partial Synchrony: Balancing Speed & Accuracy
Open Access
- 12 October 2024
- book chapter
- Published by Springer Nature
- p. 282-301
Abstract
In distributed systems with processes that do not share a global clock, 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 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 20 references indexed in Scilit:
- Quantitative Safety and Liveness2023
- Abstract Monitors for Quantitative Specifications2022
- On Benchmarking for Concurrent Runtime Verification2021
- 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
- Detecting Temporal Logic Predicates on Distributed ComputationsLecture Notes in Computer Science, 2007
- Techniques and applications of computation slicingDistributed Computing, 2005