Approximate Distributed Monitoring under Partial Synchrony: Balancing Speed and Accuracy
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866916351267831808 |
|---|---|
| author | Bonakdarpour, Borzoo Momtaz, Anik Ničković, Dejan Saraç, N. Ege |
| author_facet | Bonakdarpour, Borzoo Momtaz, Anik Ničković, Dejan Saraç, N. Ege |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_05033 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Approximate Distributed Monitoring under Partial Synchrony: Balancing Speed and Accuracy Bonakdarpour, Borzoo Momtaz, Anik Ničković, Dejan Saraç, N. Ege Logic in Computer Science 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. |
| title | Approximate Distributed Monitoring under Partial Synchrony: Balancing Speed and Accuracy |
| topic | Logic in Computer Science |
| url | https://arxiv.org/abs/2408.05033 |