Skip to Main content Skip to Navigation
Journal articles

Organising LTL Monitors over Distributed Systems with a Global Clock

Christian Colombo 1 yliès Falcone 2, 3, * 
* Corresponding author
3 CORSE - Compiler Optimization and Run-time Systems
Inria Grenoble - Rhône-Alpes, LIG - Laboratoire d'Informatique de Grenoble
Abstract : Users wanting to monitor distributed systems often prefer to abstract away the architecture of the system by directly specifying correctness properties on the global system behaviour. To support this abstraction, a compilation of the properties would not only involve the typical choice of monitoring algorithm, but also the organisation of submonitors across the component network. Existing approaches, considered in the context of LTL properties over distributed systems with a global clock, include the so-called orchestration and migration approaches. In the orchestration approach, a central monitor receives the events from all subsystems. In the migration approach, LTL formulae transfer themselves across subsystems to gather local information. We propose a third way of organising submonitors: choreography, where monitors are organised as a tree across the distributed system, and each child feeds intermediate results to its parent. We formalise choreography-based decentralised monitoring by showing how to synthesise a network from an LTL formula, and give a decentralised monitoring algorithm working on top of an LTL network. We prove the algorithm correct and implement it in a benchmark tool. We also report on an empirical investigation comparing these three approaches on several concerns of decentralised monitoring: the delay in reaching a verdict due to communication latency, the number and size of the messages exchanged, and the number of execution steps required to reach the verdict.
Complete list of metadata
Contributor : Yliès Falcone Connect in order to contact the contributor
Submitted on : Friday, May 13, 2016 - 5:00:46 PM
Last modification on : Sunday, June 26, 2022 - 5:02:20 AM
Long-term archiving on: : Wednesday, November 16, 2016 - 4:40:25 AM


Files produced by the author(s)




Christian Colombo, yliès Falcone. Organising LTL Monitors over Distributed Systems with a Global Clock. Formal Methods in System Design, Springer Verlag, 2016, 49 (1-2), pp.50. ⟨10.1007/s10703-016-0251-x⟩. ⟨hal-01315776⟩



Record views


Files downloads