💻 computer science

Monitoring Diameters of Causal Communication Graph with Spatio-Temporal Logic

This paper introduces a "space horizon" operator to extend the muTGL logic, enabling the verification of distance-bounded reachability and communication chain costs in multi-agent systems, and provides a centralized offline monitoring algorithm validated on consensus-based task allocation protocols.

Original authors: Lydia Bakiri, Jérémy Dubut, Sergio Mover

Published 2026-06-23

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Lydia Bakiri, Jérémy Dubut, Sergio Mover

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a fleet of drones flying together, or a group of autonomous cars driving in a convoy. They need to talk to each other to stay safe and get their jobs done. But here's the catch: they are moving, the wind changes, and sometimes one drone might lose its signal. Because they are moving, the "map" of who can talk to whom is constantly changing.

This paper is about a new way to check if these moving groups are talking to each other correctly, specifically looking at how far a message has to travel and how long it takes.

Here is the breakdown of the problem and the solution, using simple analogies:

The Problem: The "Telephone Game" with Moving People

Imagine you are playing the "Telephone Game" (where a message is whispered from person to person).

The Old Way: Previous tools could tell you, "Did the message get from Person A to Person B?" or "Did it take less than 5 seconds?"
The Missing Piece: They couldn't easily answer: "Did the message get from A to B without passing through more than 3 people?" or "Did it travel a total distance of less than 10 miles?"

In a moving group, this matters. If a message has to hop through 50 drones to get across the group, the system is slow and uses too much battery. If the "chain" of communication is too long, the group might break apart or fail to agree on what to do.

The authors call this the "Diameter of the Causal Communication Graph."

Causal: It respects time. If Drone A talks to Drone B, and then B talks to C, A can influence C. But if B talks to C before A talks to B, A cannot influence C. It's a one-way street in time.
Diameter: The longest "hop" count or distance a message needs to travel to reach anyone in the group.

The Solution: A New "Ruler" for the Logic

The authors created a new tool (an extension of a logic called µ-TGL) that adds a "Space Horizon."

Think of the old logic as having a Time Ruler. You could say, "Check if the message arrives within 10 seconds."
The new logic adds a Space Ruler. You can now say, "Check if the message arrives within 10 seconds AND within 5 hops (or 5 miles)."

They introduced a new operator (a special command in their language) called the Space Horizon.

Analogy: Imagine you are looking at a map with a flashlight.
- The Time Horizon is how far into the future your flashlight shines.
- The Space Horizon is how far out from your current location your flashlight shines.
- The new tool lets you set a limit on the flashlight's reach in both directions simultaneously.

How It Works (The "Offline" Monitor)

The paper describes a computer program that acts like a post-game referee.

The Input: It takes a recording (a "trace") of how the drones moved and talked over time.
The Check: It runs the new logic against the recording. It asks questions like: "At any point in this recording, did a message have to jump more than 4 drones to get across the group?"
The Result: It produces a report saying, "Yes, between 2:00 PM and 2:05 PM, the group was too spread out, and messages had to travel too far."

The "Tricky" Part: Handling the Unknown

In real life, you don't always have the full recording immediately. You might be watching the drones live, and you haven't seen the future yet.

The logic uses a special "Maybe" value. If the system hasn't seen enough of the future to know if a message will arrive, it says "Maybe."
The authors had to be very careful with math to make sure the computer doesn't get stuck in an infinite loop trying to figure out these "Mays." They proved that their method always finishes its calculation.

The Real-World Test

To prove it works, they simulated a group of 10 drones trying to visit 100 different locations (a task allocation problem).

They used a standard algorithm called CBBA (Consensus-Based Bundle Algorithm) where drones bid on tasks.
They ran their new monitoring tool on the simulation data.
The Result: The tool successfully identified exactly when the group's communication network was efficient (short chains) and when it was inefficient (long chains). It could tell them, for example, "The group was fully connected for 10 minutes, but then the diameter grew, meaning messages took longer to travel."

Summary

The paper introduces a new mathematical "ruler" that can measure not just when things happen, but also how far information has to travel through a moving group. They built a computer program that uses this ruler to analyze recordings of drone swarms, proving it can spot when communication chains get too long and slow down the system.

Key Takeaway: It's a new way to check if a moving team is staying close enough together to talk efficiently, without needing to wait for the future to happen.

Technical Summary: Monitoring Diameters of Causal Communication Graph with Spatio-Temporal Logic

1. Problem Statement

The verification of multi-agent systems (MAS) operating in continuous space and time faces significant challenges due to the dynamic nature of their communication topologies. In systems such as autonomous vehicle fleets or drone swarms, communication links are not static; they evolve as agents move, creating causal communication chains where information flow is inherently directed and time-dependent.

Existing formal verification methods often struggle with these dynamics. While µ-TGL (Timed Graph Logic with fixpoint) offers a framework for expressing entangled spatio-temporal properties using fixpoint operators, it possesses a critical limitation: it lacks the expressivity to analyze reachability within specific distance bounds or to track the length and cost of communication chains. Specifically, vanilla µ-TGL cannot constrain the spatial propagation of information (e.g., limiting a chain to a specific number of hops or a maximum spatial cost). This capability is fundamental for decentralized monitoring and the analysis of distributed protocols (such as consensus or task allocation), where algorithmic complexity and resource consumption (energy, rounds of communication) are directly tied to the diameter of the communication graph.

2. Methodology

The authors propose an extension to µ-TGL and a corresponding offline monitoring algorithm to address these limitations.

2.1 Logic Extension: The Space Horizon

The core contribution is the introduction of a new operator, the space horizon ( $\bullet_s \phi$ ), which mirrors the existing time horizon ( $H_h \phi$ ) in µ-TGL.

Syntax: The grammar is extended to include $\bullet_s \phi$ , where $s$ is a non-negative real number representing a spatial budget (e.g., distance or communication cost).
Semantics: The semantics are extended from a function of type $\mathbb{R}_{\ge 0} \times \mathbb{R} \times A \to \mathbb{3}$ $R_{\geq 0} \times R \times A \to 3$ (time, time-budget, agent) to $\mathbb{R}_{\ge 0} \times \mathbb{R} \times \mathbb{R} \times A \to \mathbb{3}$ $R_{\geq 0} \times R \times R \times A \to 3$ , adding a space horizon parameter.
- The semantics track both time and space budgets explicitly.
- The spatial modality ( $\Diamond_D$ ) is redefined to respect the space budget: an edge between agents is valid only if its weight falls within the target interval $D$ and does not exceed the remaining space budget.
- The space horizon operator $\bullet_s$ acts as a constraint: it evaluates the inner formula with a space budget of $s$ . If the formula requires more space than $s$ to be determined, the result may be indeterminate ( $\top\bot$ ) or false, depending on the context.
Expressiveness: This extension allows the encoding of global properties like Reach (connectivity within a cost bound) and Escape (propagation beyond a cost bound) in a causal, timed manner, which were previously only available in untimed logics like STREL.

2.2 Monitoring Algorithm

The paper presents a centralized offline monitoring algorithm capable of evaluating these extended specifications.

Data Structure: The algorithm operates on "discrete signals," representing the timed graph as a sequence of samples where the graph is piecewise-constant between time steps. The output is a nested signal structure representing truth values over time, time-horizon, and space-horizon.
Termination and Bounding: A major technical challenge is ensuring the termination of fixpoint computations in the presence of unbounded information requirements.
- The authors prove that for a bounded time horizon $T$ and a bounded space horizon $s$ , the computation only requires a finite amount of information.
- They construct finite sets of time points, time budgets, and space budgets derived from the formula structure and the input signal.
- By restricting the computation to these finite sets, they prove that the fixpoint iterations terminate in a finite number of steps.
Three-Valued Semantics: The algorithm utilizes a three-valued logic ( $\top, \bot, \top\bot$ ) to handle situations where observations are insufficient to determine satisfaction or violation, a necessity for online monitoring scenarios.

3. Key Contributions

Syntactic and Semantic Extension: The introduction of the space horizon operator ( $\bullet_s$ ) to µ-TGL, enabling the specification of spatially bounded causal communication chains.
Expressiveness Proof: Demonstration that the extended logic can encode modalities such as Reach and Escape in a causal, timed context, strictly increasing the expressiveness over vanilla µ-TGL.
Termination Guarantee: A formal proof that the monitoring algorithm terminates for bounded time and space horizons, despite the presence of fixpoint operators and the need to track spatial budgets.
Implementation and Case Study: Implementation of the algorithm in OCaml and its application to Consensus-Based Bundle Algorithms (CBBA), a distributed protocol for task allocation.

4. Results

The authors evaluated their approach using simulations of 10 agents performing task allocation in a 2D area.

Diameter Monitoring: The algorithm successfully monitored the diameter of the causal communication graph over time. It identified specific time intervals where the graph was fully connected (diameter $\le 6$ ) and intervals where connectivity was sparse (diameter never reaching 1, i.e., not a clique).
Chain Length Analysis: The system monitored the maximum length of communication chains required for agents to reach a specific target, providing insights into the efficiency of the distributed protocol.
Scalability:
- For 10 agents, the monitoring took an average of 267 seconds for a trace of ~12,000 time steps (approx. 0.022s per time step).
- Scalability tests varying the number of agents ( $n \in [3, 50]$ ) showed that monitoring a specification bounded by $n/2$ scales well up to 30 agents (avg. 17ms per time step).
- For 50 agents, the time increased to 142ms per time step. The authors note that while this is acceptable for low-velocity physical systems, monitoring global diameter (requiring checks for all agents) would be computationally prohibitive for larger systems.

5. Significance and Claims

The paper claims that this work addresses a fundamental gap in the formal verification of distributed, mobile multi-agent systems. By enabling the specification and monitoring of bounded causal communication diameters, the logic provides a tool to verify critical performance metrics (like protocol round counts and energy consumption) that depend on graph topology.

The authors emphasize that while the current implementation is an offline algorithm, the careful design of the semantics (specifically the handling of indeterminate values and horizons) lays the groundwork for online monitoring. They position this as a step toward integrating such logic into control loops as a "safety shield" or for runtime filtering of decisions in decentralized systems. The work does not claim to solve the scalability issues of fully centralized monitoring for large-scale systems but demonstrates feasibility for moderate-sized systems and highlights the path toward decentralized monitoring where individual agents monitor their local reachability constraints.