Approximate Distributed Monitoring under Partial Synchrony: Balancing Speed and Accuracy

arXiv:2408.05033 · cs.LO · Submitted 2024-08-09 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.

Tom: I'm Tom.

Jane: And I'm Jane, here with Lu, Meng and our in-house large language model, Lalam.

Tom: We're looking at the paper: "Approximate Distributed Monitoring under Partial Synchrony".

Jane: Here's the gist of the paper. In distributed systems without global clocks, partial synchrony is achieved through clock synchronization that ensures bounded clock skew among all applications <ref:2408.05033#pg2> Existing solutions for distributed runtime verification under partial synchrony against temporal logic specifications are exact but suffer from significant computational overhead <ref:2408.05033#pg3>.

Tom: 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 <ref:2408.05033#pg2>.

Jane: This conservative abstraction enables a significant speedup of the distributed monitors, albeit with a tradeoff in accuracy <ref:2408.05033#pg2>.

Tom: Problem Context Formal verification of distributed system correctness is notoriously hard due to the combinatorial explosion of all possible interleavings in the behaviors collected from individual agents <ref:2408.05033#pg3>.

Title and authors: Tom: So, we’re looking at this paper titled "Approximate Distributed Monitoring under Partial Synchrony: Balancing Speed and Accuracy." It sounds like it’s tackling the problem of checking if a distributed system is behaving correctly when you don't have a perfect global clock.

Jane: That’s the core issue, right? In systems without a global clock, you only get partial synchrony, which means some applications might be slightly out of sync with each other. The authors are proposing an approximate distributed monitoring algorithm for Signal Temporal Logic, or STL specifications.

Lu: They’re focusing on how to handle those timing uncertainties by abstracting away the potential interleaving behaviors in the system's collected traces. That’s a big step because usually, when you monitor something distributed, you have to consider every possible way those independent agents could interleave their actions, which leads to a massive combinatorial explosion.

Meng: But that combinatorial explosion is what makes exact solutions computationally prohibitive for runtime verification under partial synchrony, right? If we try to check every single interleaving combination with an SMT solver, it just blows up the computation time way too fast.

Lalam: Exactly. The paper addresses this by using a conservative abstraction to simplify those behaviors into sets of Boolean expressions, which helps speed things up significantly but sacrifices some of the precision you’d get from an exact check.

Tom: So, they’re not aiming for perfect accuracy on every possible execution path, but they’re trying to achieve a meaningful speedup for runtime verification in this tricky partial synchrony setting. That sounds like a pragmatic trade-off.

Jane: Right. The implication here is that we can get verification done faster in real-world distributed systems where clock synchronization isn't perfect, even if the monitor isn't one hundred percent precise about every single timing nuance.

The paper's summary: Jane: So, what’s the actual technical mechanism they are proposing for this approximate monitoring? They are using a conservative abstraction to represent distributed behaviors as an overapproximation.

Lu: They define this overapproximation Tr plus S, which is essentially taking the set of all possible traces and making it bigger by including all traces that *could* happen given the uncertainty regions caused by clock skews. That means you’re checking a slightly larger set of possibilities than what actually occurs.

Tom: And they use this overapproximated set to define monitoring operations that evaluate the temporal specifications, which gives them a verdict on those overapproximated behaviors. It’s about translating the complex timing problem into evaluating these simpler, overapproximated expressions.

Meng: I'm curious about how they handle those clock skews specifically in their abstraction. Does it just lump everything together?

Jane: Not exactly; they say the abstraction simplifies distributed behaviors into a set of Boolean expressions that account for the regions of uncertainty created by those clock skews, which is what lets them move forward. They define these monitoring operations to yield verdicts on these overapproximated behaviors.

Lu: The idea is that this conservative abstraction lets them bypass the need to explicitly deal with every single interleaving combination, which is where the computational explosion happens in exact methods for distributed runtime verification under partial synchrony <ref:2408.05033#pg2>.

Tom: So, the key takeaway here is that they’re trading off a bit of accuracy for a significant speedup in their distributed monitors. That’s what they are balancing: efficiency versus precision.

The paper's improvements: Jane: When we look at how this approach improves things over existing exact methods, the main thing is that it tackles the computational overhead head-on by using this abstraction.

Lu: They move away from relying solely on SMT solving for every possible trace because that’s too slow; they introduce a new way to evaluate satisfaction signals of formulas without explicitly computing that massive set of all possible traces, which they call Tr plus S, <ref:2408.05033#pg3>.

Tom: So, the improvement is moving from an exact check over an exponential number of possibilities to a fast check over an approximated set of behaviors. It’s about simplifying the representation into Boolean expressions instead of dealing with the full trace space.

Meng: From a production standpoint, speed is good, but accuracy matters for deployment. So what about that trade-off they mention? How much accuracy are we losing compared to the exact methods?

Jane: They acknowledge that there’s an inevitable tradeoff between accuracy and speedup <ref:2408.05033#pg2>. But they actually suggest a methodology where you combine their approximate monitor with its exact counterpart, resulting in enhanced efficiency without sacrificing precision when needed.

Lu: So, if the approximate check gives a result that seems questionable or inconclusive, you can then run the full exact check on that specific case to confirm the result before deciding. That sounds like a smart way to manage risk while keeping things fast most of the time <ref:2408.05033#pg2>.

Tom: That combined approach actually makes sense from an engineering standpoint; you use the fast approximation for most cases, and only pay the high cost of the exact method when you really need that certainty.

Conclusion: Jane: So, wrapping up this discussion on "Approximate Distributed Monitoring under Partial Synchrony: Balancing Speed and Accuracy," we see they’ve developed a modular procedure for monitoring distributed Signal Temporal Logic that is much faster than the older SMT-based methods.

Lu: The paper shows that by abstracting away potential interleaving behaviors through an overapproximation, you can achieve speedups of three to five orders of magnitude over exact methods <ref:2408.05033#pg2>. This is particularly effective when dealing with long signals and low uncertainty bounds.

Tom: It’s interesting that the speedup depends on things like the type of specification, how long the input signal lasts, and even the maximal clock skew they allow <ref:2408.05033#pg2>. That tells us this isn't a magic fix; it’s context-dependent efficiency.

Meng: For deployment at scale, having an algorithm that gives you massive speedup is appealing, but we always have to consider what breaks when the system is under heavy load or has unexpected timing issues.

Lalam: The authors state their limitation clearly: while they propose this approximation, they also devise a methodology that combines the approximate and exact monitors to benefit from enhanced efficiency without sacrificing precision <ref:2408.05033#pg2>. That’s their way of managing that inherent accuracy tradeoff.

Jane: Overall, the implication is that we now have a practical tool for distributed STL monitoring in partial synchrony settings where computational cost used to be too high. We should look forward to them extending this approach into the online setting and exploiting the modular nature of these monitors for better control over their accuracy in future work.

Tom: Yeah, they’re planning to extend it online, which is a big challenge because you can't just re-run the check; you have to monitor continuously while things are happening. But having that control over accuracy sounds like the right path forward for real systems.

Borzoo Bonakdarpour, Anik Momtaz, Dejan NiČkovišc, N. Ege Saranj

Michigan State University · AIT Austrian Institute of Technology · Institute of Science and Technology Austria

cs.LO

Submitted: 2024-08-09

Updated: 2026-11-16

Comments: To appear in the STTT special issue of RV 2024

Code: https://github.com/egesarac/ApxDistMon

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 91/100

The gist: In distributed systems without global clocks, partial synchrony is achieved through clock synchronization that ensures bounded clock skew among all applications <ref:2408.05033#pg2> Existing…

Key concepts

Partial Synchrony
This is a condition in distributed systems where clocks are not perfectly synchronized globally, but they are guaranteed to be within a bounded time difference. This constraint allows the system to operate reliably despite clock drift among different agents.
Runtime Verification (RV)
RV is a method where the correctness of a distributed system's behavior is checked against formal specifications while it is running. The challenge here is that observing one behavior doesn't reveal all possible interleavings, leading to verification complexity.
Approximate Monitoring
This technique simplifies the verification process by abstracting away complex interleaving behaviors into overapproximations. Instead of checking every possible sequence of events, it checks a simplified set of possibilities, drastically reducing computational load at the cost of potential inaccuracy.

Terminology

Summary

In distributed systems without global clocks, partial synchrony is achieved through clock synchronization that ensures bounded clock skew among all applications <ref:2408. p. 0

Where the paper says it

at 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.

05033#pg2> Existing solutions for distributed runtime verification under partial synchrony against temporal logic specifications are exact but suffer from significant computational overhead <ref:2408. p. 0
Where the paper says it

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.

05033#pg3>. 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 <ref:2408. p. 0
Where the paper says it

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.

05033#pg2>. This conservative abstraction enables a significant speedup of the distributed monitors, albeit with a tradeoff in accuracy <ref:2408. p. 0
Where the paper says it

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.

05033#pg2>.

Problem Context

Formal verification of distributed system correctness is notoriously hard due to the combinatorial explosion of all possible interleavings in the behaviors collected from individual agents <ref:2408.05033#pg3>. Runtime verification (RV) provides a pragmatic approach where a behavior of a distributed system is observed and its correctness is checked against a formal specification <ref:2408. p. 0

Where the paper says it

Formal verification of distributed system is a notoriously hard problem, due to the combinatorial explosion of all possible interleavings in the behaviors collected from individual agents. Runtime verification (RV) provides a more pragmatic approach in which a behavior of a distributed system is observed and its ⋆ This work was supported in part by the ERC-2020-AdG 101020093.

05033#pg2>. The problem of distributed RV under partial synchrony assumption has been studied for Linear Temporal Logic (LTL) [11] and Signal Temporal Logic (STL) [18] specification languages <ref:2408. p. 1
Where the paper says it

Remotely related to the problem of distributed RV under partial synchrony are distributed RV in the fully synchronous [9,8,5] and asynchronous [7,17,21,19,12,6] settings as well as benchmarking tools [2] for assessing monitoring overhead. The problem of distributed RV under partial synchrony assumption has been studied for Linear Temporal Logic (LTL) [11] and Signal Temporal Logic (STL) [18] specification languages.

05033#pg3>. Although distributed RV monitors consume only a single distributed behavior at a time, this behavior can have an excessive number of possible interleavings <ref:2408. p. 1
Where the paper says it

The proposed solutions use Satisfiability-Modulo-Theory (SMT) solving to provide sound and complete distributed monitoring procedures. Although distributed RV monitors consume only a single distributed behavior at a time, this behavior can have an excessive number of possible interleavings.

05033#pg3>. Hence, the exact distributed monitors from the literature can still suffer from significant computational overhead <ref:2408. p. 1
Where the paper says it

Put another way, although RV deals only with the verification of a single execution at run time, it is still prone to evaluating an explosion of combinations. Hence, the exact distributed monitors from the literature can still suffer from significant computational overhead.

05033#pg2>.

Approximate Monitoring Methodology

To mitigate this issue, we propose a new approach for approximate RV of STL under partial synchrony by conservatively abstracting away potential interleavings in distributed behaviors, resulting in their overapproximation <ref:2408.05033#pg2>. This abstraction simplifies the representation of distributed behaviors into a set of Boolean expressions, taking into account regions of uncertainty created by clock skews <ref:2408. p. 1

Where the paper says it

In essence, we conservatively abstract away potential interleavings in distributed behaviors, resulting in their overapproximation. This abstraction simplifies the representation of distributed behaviors into a set of Boolean expressions, taking into account regions of uncertainty created by clock skews.

05033#pg2>. We define monitoring operations that evaluate temporal specifications over such expressions, which result in monitoring verdicts on overapproximated behaviors <ref:2408. p. 1
Where the paper says it

This abstraction simplifies the representation of distributed behaviors into a set of Boolean expressions, taking into account regions of uncertainty created by clock skews. We define monitoring operations that evaluate temporal specifications over such expressions, which result in monitoring verdicts on overapproximated behaviors.

05033#pg2>. This approximate solution yields an inevitable tradeoff between accuracy and speedup <ref:2408. p. 1
Where the paper says it

We define monitoring operations that evaluate temporal specifications over such expressions, which result in monitoring verdicts on overapproximated behaviors. This approximate solution yields an inevitable tradeoff between accuracy and speedup.

05033#pg2>. For applications where reduced accuracy is not acceptable, we devise a methodology that combines approximate and exact monitors, with the aim to benefit from the enhanced efficiency without sacrificing precision <ref:2408. p. 1
Where the paper says it

This approximate solution yields an inevitable tradeoff between accuracy and speedup. For applications where reduced accuracy is not acceptable, we devise a methodology that combines approximate and exact monitors, with the aim to benefit from the enhanced efficiency without sacrificing precision.

05033#pg2>.

Overapproximation of Traces

We describe an overapproximation Tr+(S, ⇝) of its set Tr(S, ⇝) of synchronous traces by first presenting the notion of canonical segmentation <ref:2408.05033#pg2>. The canonical segmentation GS is defined as the segmentation where the segment endpoints match the temporal domain and uncertainty region endpoints <ref:2408. p. 5

Where the paper says it

Let (S, ⇝) be a distributed signal of n signals. The canonical segmentation GS of (S, ⇝) the segmentation of S where the segment endpoints match the temporal domain and uncertainty region endpoints.

05033#pg2>. We define a function γ: S × GS → 2Σ∗ that maps each signal and segment of the canonical segmentation to a set of value expressions, capturing the signal’s potential behaviors in the given segment <ref:2408. p. 6
Where the paper says it

Similarly, the behavior in [4, 5) is given by suffix(v1) · prefix(v2), which captures whether the edges occur in this interval (thanks to prefixing and suffixing) and the fact that the rising edge happens before the falling edge (thanks to concatenation). Formally, given a distributed signal (S, ⇝), we define a function γ : S × GS → 2 Σ∗ that maps each signal and segment of the canonical segmentation to a set of value expressions, capturing the signal’s potential behaviors in the given segment.

05033#pg2>. The set Tr+(S, ⇝) is then defined as Tr+(S, ⇝) = (x′1,. p. 2
Where the paper says it

, σm,1σm,2vm) of words of the same length, destutter(u1, . , um) is defined as expected: destutter(u1, .

.. x′n) x′i is consistent with xi for all 1 ≤ i ≤ n <ref:2408. p. 0
Where the paper says it

101096658). arXiv:2408.

05033#pg3>.

Monitoring Algorithm

We describe an algorithm to compute [(S, ⇝) = φ]+ using the function γ from Section 4 without explicitly computing Tr+(S, ⇝) <ref:2408.05033#pg2>. This involves introducing the asynchronous product of value expressions to capture interleavings within segments <ref:2408. p. 7

Where the paper says it

5 Monitoring Algorithm In this section, for a distributed signal (S, ⇝), we describe an algorithm to compute [(S, ⇝) |= φ]+ using the function γ from Section 4 without explicitly computing Tr+(S, ⇝). We introduce the asynchronous product of value expressions to capture interleavings within segments, then evaluate untimed and timed operators.

05033#pg2>. We then apply bitwise operations on value expressions and their asynchronous products to transform them into encodings of satisfaction signals of formulas <ref:2408. p. 8
Where the paper says it

Untimed Operations. As hinted in Example 2, to compute the semantics, we apply bitwise operations on value expressions and their asynchronous products to transform them into encodings of satisfaction signals of formulas.

05033#pg2>. Finally, we combine these steps to compute the semantics of STL+ <ref:2408. p. 7
Where the paper says it

We introduce the asynchronous product of value expressions to capture interleavings within segments, then evaluate untimed and timed operators. Finally, we combine these steps to compute the semantics of STL+.

05033#pg2>.

Experimental Evaluation

We evaluate our approach with multiple experiments, showcasing its efficacy in both real-world applications and synthetic examples <ref:2408.05033#pg2>. We find that Adm consistently achieves speedups of three to five orders of magnitude over Edm <ref:2408. p. 1

Where the paper says it

We implemented our approach in a prototype tool and performed thorough evaluations on both synthetic and real-world case studies (mutual separation in swarm of drones and a water distribution system). We first demonstrated that in many experiments, our approximate monitors achieve speedups of up to 5 orders of magnitude compared to the exact SMT-based solution.

05033#pg2>. The speedup depends on the type of specifications, input signal duration, and maximal clock skew <ref:2408. p. 0
Where the paper says it

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.

05033#pg2>. Combining Adm and Edm still results in significant gains, positively answering RQ2 <ref:2408. p. 1
Where the paper says it

We empirically characterized the classes of specifications and behaviors for which our approximate monitors achieve good precision. We finally showed that combining exact and approximate distributed RV yields significant efficiency gains on average without sacrificing precision, even with low-accuracy approximate monitors.

05033#pg2>.

Conclusion

We presented an approximate, modular procedure for distributed STL monitoring that significantly improves efficiency over exact SMT-based methods <ref:2408.05033#pg2>. We plan to extend our monitoring approach to the online setting <ref:2408. p. 1

Where the paper says it

Approximate monitoring is also valuable in the sequential setting, with applications including monitoring with state estimation [23,4], quantitative monitoring and its resource-precision tradeoffs [15,13,14], and various other uses [3,1]. We implemented our approach in a prototype tool and performed thorough evaluations on both synthetic and real-world case studies (mutual separation in swarm of drones and a water distribution system).

05033#pg2>. We will also exploit the modular nature of our monitors to have a better control over their accuracy <ref:2408. p. 0
Where the paper says it

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.

05033#pg2>.

References

  1. Aceto, L., Achilleos, A., Francalanza, A., Ingólfsdóttir, A., Lehtinen, K.: The best a monitor can do. p. 0

    Where the paper says it

    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.

    In: Baier, C., Goubault-Larrecq, J. (eds.) 29th EACSL Annual Conference on Computer Science Logic, CSL 2021, January 25-28, 2021, Ljubljana, Slovenia (Virtual Conference). LIPIcs, vol. 183, pp. 7:1–7:23

  2. Bartocci, E., Grosu, R.: Monitoring with uncertainty. p. 1

    Where the paper says it

    This abstraction simplifies the representation of distributed behaviors into a set of Boolean expressions, taking into account regions of uncertainty created by clock skews. We define monitoring operations that evaluate temporal specifications over such expressions, which result in monitoring verdicts on overapproximated behaviors.

    In: Bortolussi, L., Bujorianu, M., Pola, G. (eds.) Proceedings Third International Workshop on Hybrid Autonomous Systems, HAS 2013, Rome, Italy, 17th March 2013. p. 9
    Where the paper says it

    Second, given an interval K, we respectively denote by lK and rK its left and right end points. Third, recall that we denote by F the set of end points of GS (see Section 4).

    EPTCS, vol. 124, pp. 1–4

  3. Bauer, A., Falcone, Y.: Decentralised LTL monitoring. p. 1

    Where the paper says it

    Remotely related to the problem of distributed RV under partial synchrony are distributed RV in the fully synchronous [9,8,5] and asynchronous [7,17,21,19,12,6] settings as well as benchmarking tools [2] for assessing monitoring overhead. The problem of distributed RV under partial synchrony assumption has been studied for Linear Temporal Logic (LTL) [11] and Signal Temporal Logic (STL) [18] specification languages.

    Formal Methods in System Design 48(1-2), 46–93 (2016)

  4. Colombo, C., Falcone, Y.: Organising LTL monitors over distributed systems with a global clock. p. 0

    Where the paper says it

    at 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.

    Formal Methods in System Design 49(1-2), 109–158 (2016)

  5. Ganguly, R., Momtaz, A. p. 0

    Where the paper says it

    Approximate Distributed Monitoring under Partial Synchrony: Balancing Speed & Accuracy ⋆ Borzoo Bonakdarpour 1 , Anik Momtaz 1 , Dejan Ničković 2 , and N. Ege Saraç 3 1 Michigan State University {borzoo,momtazan}@msu.

    , Bonakdarpour, B. p. 0
    Where the paper says it

    Approximate Distributed Monitoring under Partial Synchrony: Balancing Speed & Accuracy ⋆ Borzoo Bonakdarpour 1 , Anik Momtaz 1 , Dejan Ničković 2 , and N. Ege Saraç 3 1 Michigan State University {borzoo,momtazan}@msu.

    p. 0
    Where the paper says it

    Approximate Distributed Monitoring under Partial Synchrony: Balancing Speed & Accuracy ⋆ Borzoo Bonakdarpour 1 , Anik Momtaz 1 , Dejan Ničković 2 , and N. Ege Saraç 3 1 Michigan State University {borzoo,momtazan}@msu.

    p. 0
    Where the paper says it

    Approximate Distributed Monitoring under Partial Synchrony: Balancing Speed & Accuracy ⋆ Borzoo Bonakdarpour 1 , Anik Momtaz 1 , Dejan Ničković 2 , and N. Ege Saraç 3 1 Michigan State University {borzoo,momtazan}@msu.

    : Runtime verification of partiallysynchronous distributed system. p. 0
    Where the paper says it

    Formal verification of distributed system is a notoriously hard problem, due to the combinatorial explosion of all possible interleavings in the behaviors collected from individual agents. Runtime verification (RV) provides a more pragmatic approach in which a behavior of a distributed system is observed and its ⋆ This work was supported in part by the ERC-2020-AdG 101020093.

    In: Bramas, Q., Oshman, R., Romano, P. (eds.) 24th International Conference on Principles of Distributed Systems, OPODIS 2020, December 14-16, 2020, Strasbourg, France (Virtual Conference). p. 0
    Where the paper says it

    Formal verification of distributed system is a notoriously hard problem, due to the combinatorial explosion of all possible interleavings in the behaviors collected from individual agents. Runtime verification (RV) provides a more pragmatic approach in which a behavior of a distributed system is observed and its ⋆ This work was supported in part by the ERC-2020-AdG 101020093.

    LIPIcs, vol. 184, pp. 20:1–20:17

  6. Henzinger, T.A., Mazzocchi, N., Saraç, N. p. 0

    Where the paper says it

    Approximate Distributed Monitoring under Partial Synchrony: Balancing Speed & Accuracy ⋆ Borzoo Bonakdarpour 1 , Anik Momtaz 1 , Dejan Ničković 2 , and N. Ege Saraç 3 1 Michigan State University {borzoo,momtazan}@msu.

    p. 0
    Where the paper says it

    Approximate Distributed Monitoring under Partial Synchrony: Balancing Speed & Accuracy ⋆ Borzoo Bonakdarpour 1 , Anik Momtaz 1 , Dejan Ničković 2 , and N. Ege Saraç 3 1 Michigan State University {borzoo,momtazan}@msu.

    E.: Abstract monitors for quantitative specifications. p. 1
    Where the paper says it

    For applications where reduced accuracy is not acceptable, we devise a methodology that combines approximate and exact monitors, with the aim to benefit from the enhanced efficiency without sacrificing precision. Approximate monitoring is also valuable in the sequential setting, with applications including monitoring with state estimation [23,4], quantitative monitoring and its resource-precision tradeoffs [15,13,14], and various other uses [3,1].

    In: Dang, T., Stolz, V. (eds.) Runtime Verification - 22nd International Conference, RV 2022, Tbilisi, Georgia, September 28-30, 2022

  7. Henzinger, T.A., Saraç, N.E.: Quantitative and approximate monitoring. p. 1

    Where the paper says it

    For applications where reduced accuracy is not acceptable, we devise a methodology that combines approximate and exact monitors, with the aim to benefit from the enhanced efficiency without sacrificing precision. Approximate monitoring is also valuable in the sequential setting, with applications including monitoring with state estimation [23,4], quantitative monitoring and its resource-precision tradeoffs [15,13,14], and various other uses [3,1].

    In: 36th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2021, Rome, Italy, June 29 - July 2, 2021

  8. Momtaz, A., Abbas, H., Bonakdarpour, B.: Monitoring signal temporal logic in distributed cyber-physical systems. p. 0

    Where the paper says it

    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.

    In: Mitra, S., Venkatasubramanian, N., Dubey, A., Feng, L., Ghasemi, M., Sprinkle, J. (eds.) Proceedings of the ACM/IEEE 14th International Conference on Cyber-Physical Systems, ICCPS 2023

  9. Mostafa, M., Bonakdarpour, B.: Decentralized runtime verification of LTL specifications in distributed systems. p. 0

    Where the paper says it

    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: Proceedings of the 29th IEEE International Parallel and Distributed Processing Symposium (IPDPS). pp. 494–503

  10. de Moura, L.M., Bjørner, N.S.: Z3: an efficient SMT solver. p. 7

    Where the paper says it

    Finally, we combine these steps to compute the semantics of STL+. We also discuss an efficient implementation of the monitoring algorithm using bit vectors, heuristics to enhance generalization for real-valued signals, and a method to combine our approach with exact monitoring.

    In: Ramakrishnan, C.R., Rehof, J. (eds.) Tools and Algorithms for the Construction and Analysis of Systems, 14th International Conference, TACAS 2008

  11. Stoller, S.D., Bartocci, E., Seyster, J., Grosu, R., Havelund, K., Smolka, S.A., Zadok, E.: Runtime verification with state estimation. p. 1

    Where the paper says it

    For applications where reduced accuracy is not acceptable, we devise a methodology that combines approximate and exact monitors, with the aim to benefit from the enhanced efficiency without sacrificing precision. Approximate monitoring is also valuable in the sequential setting, with applications including monitoring with state estimation [23,4], quantitative monitoring and its resource-precision tradeoffs [15,13,14], and various other uses [3,1].

    In: Khurshid, S., Sen, K. (eds.) Runtime Verification - Second International Conference, RV 2011

  12. USNRC: Pressurized water reactor systems (March 2021), https://www. p. 1

    Where the paper says it

    Approximate monitoring is also valuable in the sequential setting, with applications including monitoring with state estimation [23,4], quantitative monitoring and its resource-precision tradeoffs [15,13,14], and various other uses [3,1]. We implemented our approach in a prototype tool and performed thorough evaluations on both synthetic and real-world case studies (mutual separation in swarm of drones and a water distribution system).

    nrc.gov/reading-rm/basic-ref/students/for-educators/04.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Approximate Distributed Monitoring (Adm) can achieve speedups of up to 5 orders of magnitude compared to exact SMT-based solutions for distributed Signal Temporal Logic (STL) monitoring, particularly for long signals with low uncertainty bounds and when monitoring properties without mixed conjunctive and disjunctive operations.

  2. A smart combined use of approximate and exact distributed monitors increases efficiency while preserving accuracy by computing the approximate verdict first, and only then computing the exact verdict if the approximate result is inconclusive (If the verdict is inconclusive, i.e., v = ?, then compute and return the exact verdict [(S, ⇝) = φ], else return v.).

  3. The system can monitor complex distributed properties like mutual separation in a swarm of drones by utilizing specifications such as phiSD, which requires sophisticated arithmetic operations on signals originating from different agents.

  4. For real-valued signals, the monitoring approach can be extended using Adm-F, which avoids explicit computation of asynchronous products by considering potential value sets instead of sequences when the sum of two signals is constant within a segment.

  5. The system can reduce asynchrony by running the monitor on one of the observed agents (Relative approach), using that agent’s local clock as a reference point, potentially leading to better performance in certain settings.

Abstract

In distributed systems with processes that do not share a global clock, partial synchrony can be achieved by clock synchronization that guarantees bounded clock skew among all processes. 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, albeit with a tradeoff in precision. We address this tradeoff by combining our approximate monitor with its exact counterpart, gaining efficiency without sacrificing precision. Our framework supports offline monitoring of both future and past STL, as well as online monitoring of past STL. We evaluate our approach with multiple experiments, showcasing its efficacy in both real-world applications and synthetic examples.

Related papers