⚡ electrical engineering

Partial Resilient Leader-Follower Consensus in Time-Varying Graphs

This paper introduces the concept of partial leader-follower consensus and proposes a novel Bootstrap Percolation and Mean Subsequence Reduced (BP-MSR) algorithm that enables a subset of non-adversarial followers to track a leader's state in time-varying graphs even when standard global robustness conditions are not met.

Original authors: Haejoon Lee, Dimitra Panagou

Published 2026-03-17

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Haejoon Lee, Dimitra Panagou

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

The Big Picture: A Hiking Group with a Traitor

Imagine a large hiking group led by a guide (the Leader). The rest of the group are hikers (Followers). Their goal is simple: stay together and follow the guide's path.

However, there is a problem. One or more hikers in the group are Traitors (Adversaries). These traitors aren't just lost; they are actively trying to sabotage the group. They might shout fake directions like "Go left!" when the guide says "Go right," or they might whisper different lies to different people to cause confusion.

In the past, researchers tried to solve this by saying: "If the whole group is tightly connected enough, the truth will win." They calculated a strict rule: "You need at least 3 honest neighbors for every 1 liar to be safe."

The Problem: What happens if the group is not perfectly connected? What if the hikers are spread out, the terrain changes (Time-Varying Graphs), and the "strict rule" isn't met for the whole group? Traditional methods would say, "Okay, the whole mission is a failure; everyone stops and panics."

The New Idea: This paper says, "Wait! Even if the whole group can't be saved, maybe a part of the group can."

The Solution: The "Bootstrap" Check-In

The authors introduce a new strategy called BP-MSR (Bootstrap Percolation and Mean Subsequence Reduced). Think of this as a "Safety Check" before every step the hikers take.

Here is how it works in everyday terms:

1. The "Safety Check" (Bootstrap Percolation)

Before the hikers move, they don't just blindly follow the guide. They do a quick headcount.

The Rule: "I will only listen to the guide if I can verify that I am surrounded by enough honest people to drown out the liars."
The Process: The hikers pass a "safety token" around. If you have enough neighbors who also have the token, you get the token. If you don't, you don't.
The Result: Some hikers realize, "Hey, I'm surrounded by too many liars right now. I can't trust the signal." So, they stop moving and hold their ground. They don't update their position.

2. The "Filter" (Mean Subsequence Reduced)

The hikers who did pass the safety check (the "Active" ones) now move. But they are smart.

They look at all the directions they received.
They throw away the most extreme directions (the ones that say "Go to the moon" or "Go to the center of the earth").
They average out the remaining directions to find a safe path.

3. The "Partial Victory"

This is the magic of the paper.

Old Way: If the whole group wasn't safe, everyone failed.
New Way: The hikers who passed the safety check successfully follow the guide. The hikers who failed the check just stand still (or stay within the safe zone of the group).
The Outcome: The group doesn't collapse. A subset of the hikers (the "Convergent Set") successfully tracks the leader, while the others just wait safely until the terrain changes and they can join in later.

Why This Matters: The "Time-Varying" Terrain

Imagine the hiking trail is a shifting sand dune. Sometimes the hikers are close together; sometimes the wind blows them apart.

Traditional Algorithms are like rigid robots. If the wind blows them apart even for a second, they crash.
This New Algorithm is like a flexible team. When the wind blows them apart, the ones who are still safe keep moving. The ones who are isolated just pause. As soon as the wind shifts and they get close to safe neighbors again, they wake up and rejoin the group.

The "Traitor's Trick" (A Subtle Detail)

The paper also notes that the Traitors are tricky. They can lie about who is safe.

If a Traitor says, "I am safe!" when they aren't, they might trick an honest hiker into thinking they are safe too.
The paper proves that even if the Traitors try to manipulate the "Safety Check," there is a guaranteed range of hikers who will always succeed, no matter how the Traitors lie. It's like saying, "Even if the traitors try to trick us, we know for a fact that Hikers 6, 7, and 8 will make it to the summit."

Summary in One Sentence

Instead of giving up when a group isn't perfectly connected to fight off liars, this new method lets the safe members keep moving toward the goal while the unsafe members pause, ensuring that at least some of the group always succeeds.

The "Takeaway" for Real Life

This research is crucial for things like:

Self-driving cars: If one car's sensors are hacked, the others don't need to stop; only the ones in the "danger zone" pause, while the rest keep driving safely.
Drone swarms: If the wind scatters the drones, the ones that can still "see" each other keep forming the shape, while the scattered ones wait to be reconnected.
Social networks: It helps us understand how truth spreads in a network even when the network is broken or full of bots. Some people will still get the truth, even if the whole system isn't perfect.

1. Problem Statement

The paper addresses the challenge of resilient leader-follower consensus in multi-agent systems operating over arbitrary time-varying graphs in the presence of adversarial agents.

Context: Standard resilient consensus algorithms (e.g., Mean Subsequence Reduced or MSR) typically require the entire network to satisfy strict topological robustness conditions (such as strong $r$ -robustness) at all times to guarantee that all normal followers converge to the leader's reference state.
The Gap: In practical, energy-constrained, or dynamic environments, these global robustness conditions are often not met. Existing literature has not sufficiently explored the system behavior when these conditions fail. Specifically, it is unknown which specific followers might still succeed in tracking the leader if the global network is not robust enough.
Goal: The authors aim to characterize the behavior of the system under insufficient network robustness. Instead of requiring all followers to converge (full consensus), they introduce the concept of Partial Resilient Leader-Follower Consensus, where a specific subset of normal followers successfully tracks the leader, while others may not, but remain bounded.

2. Methodology: The BP-MSR Algorithm

To solve this problem, the authors propose a novel distributed algorithm called Bootstrap Percolation and Mean Subsequence Reduced (BP-MSR).

Core Concepts

Bootstrap Percolation (BP): A process where nodes become "active" if they have a sufficient number of active neighbors. In this context, a follower becomes active if it is part of a subgraph that satisfies the necessary robustness conditions locally.
Adversarial Model: The paper assumes an $F$ -local adversary model, where any normal agent has at most $F$ adversarial in-neighbors. Adversaries can manipulate both their consensus states and their activation states (in the BP process), but they cannot transmit non-binary values during the activation phase.

Algorithm Steps

For each time step $t$ :

Local Activation Check (Bootstrap Percolation):
- All agents run a synchronous BP process with a threshold $r = 2F + 1$ .
- Leaders are initially active.
- Followers update their activation state $q_i[t]$ based on whether they have at least $2F+1$ active neighbors (including leaders and other active followers).
- This step allows each follower to locally determine if it belongs to a strongly $(2F+1)$ -robust subgraph with respect to the set of leaders and adversaries.
Conditional Consensus Update (MSR):
- If $q_i[t] = 1$ (Active): The follower participates in the consensus update. It receives neighbor states, discards the $F$ highest and $F$ lowest values (MSR filtering), and updates its state using a convex combination of the remaining values.
- If $q_i[t] = 0$ (Inactive): The follower does not update its state ( $x_i[t+1] = x_i[t]$ ). It remains silent to prevent the propagation of potentially corrupted or unverified information.

3. Key Contributions

Partial Resilient Consensus Definition: The paper formally defines "partial resilient leader-follower consensus," acknowledging that in non-ideal networks, only a subset of followers ( $F_C$ ) may converge to the leader's state, while the rest ( $F'_C$ ) may not.
Novel BP-MSR Algorithm: The authors introduce an algorithm that enables followers to locally verify their connectivity robustness before participating in consensus. This prevents non-convergent agents from destabilizing the network.
Sufficient Conditions for Individual Convergence: Unlike previous works that rely on global network robustness, this paper establishes sufficient conditions for individual followers to converge.
- Theorem 1: A follower achieves partial consensus if it belongs to a strongly $(2F+1)$ -robust subgraph (with respect to leaders and adversaries) infinitely often.
- Safety Guarantee: Even non-convergent followers remain within the convex hull of the normal agents' states, ensuring system safety (boundedness) even if full consensus is not reached.
Characterization of the Convergent Set: The paper provides a method to bound the set of convergent followers ( $F_C$ ) based on the worst-case and best-case behaviors of adversaries regarding their activation states (Lemma 3 and Proposition 1).

4. Results and Validation

The authors validated their approach through simulations using time-varying graph sequences where global robustness conditions were explicitly not met.

Comparison with Existing Methods:
- W-MSR and SW-MSR: Standard algorithms failed to achieve consensus in the tested scenarios because the global graph sequence did not satisfy the required robustness conditions (e.g., strong $(2F+1)$ -robustness or joint robustness).
- BP-MSR: Successfully achieved partial consensus. In the simulation, followers $\{6, 7, 8\}$ converged to the leader's reference state, while followers $\{4, 5, 9\}$ did not converge but remained bounded within the convex hull of normal agents.
Convergent Set Bounds: Simulations confirmed that the size of the convergent set depends on the adversary's behavior.
- When adversaries minimized their "activation" signals, the convergent set was minimal ( $\{6, 7, 8\}$ ).
- When adversaries maximized their signals (effectively acting as leaders), the convergent set expanded ( $\{4, 5, 6, 7, 8\}$ ).
- This validated the theoretical bounds derived in Proposition 1.

5. Significance

This work represents a significant shift in the study of resilient multi-agent systems:

From "All-or-Nothing" to "Partial Success": It moves beyond the binary view of consensus (either everyone converges or the system fails) to a more nuanced understanding where partial success is guaranteed and quantifiable.
Practical Applicability: It offers a solution for systems operating in dynamic or resource-constrained environments where maintaining global network robustness is impossible.
Local Decision Making: By enabling agents to make local decisions based on their immediate connectivity, the algorithm is more scalable and robust to network partitions than global-condition-dependent algorithms.
Safety: It guarantees that even agents that cannot track the leader will not diverge to infinity or be driven to arbitrary values by adversaries, maintaining system stability.

In summary, the paper provides a rigorous framework for ensuring that a subset of agents can reliably track a leader in hostile, time-varying networks, even when the network as a whole is too weak to support full consensus.