Source-linked AI summary
Resilient Leader-Follower Consensus to Arbitrary Reference Values in Time-Varying Graphs
James Usevitch, Dimitra Panagou
TL;DR
Resilient consensus methods keep agreement within the convex hull of normal agents’ initial states, whereas leader-follower tracking may target a reference outside it. This paper presents SW-MSR conditions for resilient tracking in time-varying graphs and analyzes adversarial influence when the F-local assumption is violated, including circumstances in which selected adversaries can drive a network to arbitrary values.
Problem
Prior resilient consensus methods constrain the final value to the convex hull of normal agents’ initial states, while leader-follower tracking may require a reference outside that hull.
Source: §I · p. 1Method
The paper uses SW-MSR and strong (T, t0, r)-robustness conditions to analyze resilient leader-follower tracking in time-varying graphs.
Source: §I · pp. 1–2Results
Under sufficient conditions, a properly selected adversarial subset can drive SW-MSR agents to any arbitrary value.
Source: §I · p. 2Takeaways & Limitations
The analysis identifies F-locality as an important assumption to examine and shows that selected adversaries can drive the network to arbitrary values under stated conditions.
Source: §V · p. 6
Abstract
from arXiv · showhide
Several algorithms in prior literature have been proposed which guarantee consensus of normally behaving agents in a network that may contain adversarially behaving agents. These algorithms guarantee that the consensus value lies within the convex hull of initial normal agents' states, with the exact consensus value possibly being unknown. In leader-follower consensus problems however, the objective is for normally behaving agents to track a reference state that may take on values outside of this convex hull. In this paper we present methods for agents in time-varying graphs with discrete-time dynamics to resiliently track a reference state propagated by a set of leaders despite a bounded subset of the leaders and followers behaving adversarially. Our results are demonstrated through simulations.
I. INTRODUCTION
Prior resilient consensus methods keep normal agents’ agreement within the convex hull of their initial states, but leader-follower tracking may require following a reference outside that hull. This paper studies resilient tracking with SW-MSR in time-varying graphs and also examines when selected adversaries can drive agents to arbitrary values.
I. INTRODUCTION
- Prior MSR-family algorithms guarantee normal-agent consensus within the convex hull of their initial states, although adversarial behavior may affect the exact final value.The cited algorithms include W-MSR, SW-MSR, DP-MSR, and QW-MSR, under bounded adversaries and suitable network robustness.Source: §I · p. 1
- Leader-follower tracking extends the problem because its reference state may lie outside the convex hull of normal agents’ initial states.Prior leader-follower work typically assumes all leaders and followers follow their intended control laws.Source: §I · p. 1
- The paper gives conditions for normal agents in time-varying graphs to track leaders’ reference signals despite a bounded number of arbitrarily misbehaving agents, using SW-MSR..Source: §I · p. 1
- It introduces strong (T, t0, r)-robustness with respect to a subset as a condition used to establish resilient tracking.The authors state that this notion had not previously been defined, to their best knowledge.Source: §I · pp. 1–2
- The paper also gives sufficient conditions under which a properly selected adversarial subset can drive agents applying SW-MSR to any arbitrary value.The introduction places this result alongside concern that prior MSR results do not analyze adversarial influence when their bounds are violated.Source: §I · pp. 1–2
II. NOTATION
This section establishes notation for sets, agents, and time-varying directed communication graphs.
II. NOTATION
- R and Z denote the real numbers and integers, while R+ and Z+ denote their nonnegative subsets.Source: §II · p. 2
- The cardinality, union, intersection, and set difference of sets are written |S|, ∪, ∩, and \; indexed unions are also specified.Source: §II · p. 2
- A time-varying digraph D[t] = (V, E[t]) represents labeled agents and directed communication edges, with Vi[t] denoting agent i’s in-neighbors.An edge (i, j) means i can send information to j; the reverse edge need not exist.Source: §II · p. 2
III. PROBLEM FORMULATION
The problem formulation defines leaders and followers in a time-varying digraph, specifies SW-MSR information handling and misbehavior, and asks when normal followers converge to normal leaders’ reference state.
III. PROBLEM FORMULATION
- Leaders propagate a desired reference signal, while followers form the complementary agent set; the leader and follower sets are static and partition the network.Normally behaving leaders update their states according to the reference function.Source: §III · p. 2
- The leader and follower roles are fixed, and the network is partitioned into those two disjoint sets.Source: §III · p. 2
- The objective is for every normal follower’s state to converge to every normal leader’s state despite a possibly nonempty misbehaving subset.Normal agents and misbehaving agents are distinguished by whether they obey the specified update and communication behavior.Source: §III · p. 2
- Followers use a sliding window of recent in-neighbor information, with window length T, and SW-MSR filters values using parameter F before updating.At T = 0, SW-MSR reduces to W-MSR; the paper describes it as a generalization to time-varying edge sets.Source: §III · p. 2
- SW-MSR removes up to F extreme values above and below the follower’s current state, then forms its update from the remaining values using positive weights summing to one.The algorithm first forms a list from the most recently received neighbor values.Source: §III · p. 3
- Misbehavior includes arbitrary state updates or false or inconsistent messages; both leaders and followers may be misbehaving.Misbehaving agents include malicious and Byzantine agents, and the paper distinguishes the misbehaving and normal subsets of leaders and followers.Source: §III · pp. 2–3
A. Review of Resilient Consensus Concepts
The section reviews graph properties used to state sufficient conditions for resilient consensus, including reachability, robustness, and strong robustness relative to a subset. It introduces strong (T, t0, r)-robustness for time-varying graphs and explains how the time window relaxes per-step requirements.
A. Review of Resilient Consensus Concepts
- An F-total adversarial set has at most F nodes, while an F-local set has at most F adversarial in-neighbors for each normal agent at every t ≥ t0.These notions quantify how adversarial agents are distributed in the graph.Source: A. Review of Resilient Consensus… · p. 3
- A set is r-reachable if some node has at least r in-neighbors outside it, and a digraph is r-robust if one of every disjoint nonempty pair is r-reachable.The empty graph is 0-robust by convention, and a one-node graph is 1-robust.Source: A. Review of Resilient Consensus… · p. 3
- Strong r-robustness with respect to S requires every nonempty subset outside S to be r-reachable.Whether a digraph is strongly robust with respect to a specified S can be verified in polynomial time, whereas general r-robustness is NP-hard to determine.Source: A. Review of Resilient Consensus… · p. 3
- Strong (T, t0, r)-robustness requires the union of graphs over the preceding T steps to be strongly r-robust with respect to S for all t ≥ t0 + T.At T = 0, this reduces to strong r-robustness.Source: A. Review of Resilient Consensus… · p. 3
- The time window T relaxes the requirement for strong r-robustness at every step, allowing edges to be active less often while preserving (T, t0, r)-robustness.The paper presents this as useful when ensuring strong r-robustness at every time step is difficult in practical networks.Source: A. Review of Resilient Consensus… · p. 3
IV. RESILIENT LEADER-FOLLOWER CONSENSUS IN TIME-VARYING GRAPHS
Theorem 1 gives conditions for normally behaving followers to track normally behaving leaders in time-varying graphs despite F-local adversaries. With a constant reference, the proof establishes exponential error reduction and asymptotic tracking.
IV. RESILIENT LEADER-FOLLOWER CONSENSUS IN TIME-VARYING GRAPHS
- During a constant-reference interval, SW-MSR keeps normal followers within [m[t], M[t]], while m[t] is nondecreasing and M[t] is nonincreasing.The argument relies on filtering extreme adversarial values and taking convex combinations of retained values, including each follower’s own state.Source: §IV · p. 4
- With a constant reference, F-local adversaries, strong (T, t0, 2F + 1)-robustness with respect to the leaders, and SW-MSR parameter F, follower-leader error decreases exponentially and converges to zero on an infinite interval.The stated interval must be sufficiently long for the finite-interval result.Source: §IV · pp. 4, 6
- Strong robustness and F-locality progressively shrink the set of followers outside a narrowing interval, yielding a contraction over successive T-step windows.The proof bounds the time to empty that set by no more than (|SN f| + 1)T steps.Source: §IV · pp. 4–6
- Unlike the cited leaderless result, Theorem 1 handles Byzantine adversaries and tracks a specified leader reference that may lie outside the initial-state convex hull.The comparison in the paper is with, which considers malicious adversaries and leaderless consensus to an unknown value within that hull.Source: §IV · p. 6
V. ADVERSARIAL IMPLICATIONS
The section examines what happens when the F-local adversary assumption fails. It shows that, in a leaderless network under specified robustness and collusion conditions, adversaries can drive normal agents toward an arbitrary common value.
V. ADVERSARIAL IMPLICATIONS
- F-locality violations matter in practice because the authors note that real-world applications cannot guarantee adversaries always remain strictly F-local.They report little prior analysis of the precise effects of violating this assumption.Source: §V · p. 6
- In a leaderless network, colluding adversaries sending a common constant can drive normal agents to any value when the graph is strongly (T, t0, 2F + 1)-robust with respect to them and the interval is sufficiently long.The normal agents apply SW-MSR with parameter F; the result gives exponential error reduction toward the adversarial signal and convergence when the interval is infinite.Source: §V · p. 6
- Finding all agent subsets whose compromise could enable this outcome is left for future work.The paper identifies awareness of such strongly robust subsets as relevant when assessing a given graph.Source: §V · p. 6
VI. SIMULATIONS
The simulations demonstrate resilient tracking in time-varying k-circulant digraphs with malicious agents. They include a constant reference and a reference that changes over time.
VI. SIMULATIONS
- The framework is presented for driving agents to desired references, with examples including UAV altitude, ground-vehicle rendezvous time, and circular-patrol radius.The cited examples include reference radius for a circular patrolling path.Source: §VI · pp. 6–7
- With 15 agents, 5 leaders, F = 2, and 2 malicious agents, follower-leader error decreases exponentially while the reference remains at 30.The time window is 12 steps, and the graph switches every 4 seconds.Source: §VI · p. 7
- With 30 agents, 7 leaders, F = 3, and 3 malicious agents, follower-leader error decreases exponentially on intervals where the reference is constant.The time window is 30 steps, and the graph switches every 10 seconds.Source: §VI · p. 7
- The simulations use time-varying k-circulant digraphs that switch among three graphs whose union forms a 7-circulant digraph.Agents have no knowledge of whether their in-neighbors are normal, malicious, or leaders.Source: §VI · p. 7, Figure 1 · p. 7
VII. CONCLUSION
The paper presents conditions for discrete-time agents to resiliently track a leaders’ reference signal despite a bounded number of adversarial leaders and followers. Simulations illustrate constant and time-varying references, while future work includes time-varying graphs, asynchronous communication, and continuous-time systems.
VII. CONCLUSION
- The paper presents conditions for discrete-time agents to resiliently track a leaders’ reference signal despite a bounded number of adversarial leaders and followers.Source: §VII · p. 7
- Fig. 2 depicts SW-MSR leader-follower tracking with a constant reference and 2 malicious agents.Source: Figure 2 · p. 7
- Fig. 3 depicts SW-MSR leader-follower tracking with a time-varying reference and 3 malicious agents.Source: Figure 3 · p. 7
- Future work includes time-varying graphs, asynchronous communication, and continuous-time systems.Source: §VII · p. 7
VIII. APPENDIX: k-CIRCULANT DIGRAPHS
The appendix defines circulant graph classes and gives sufficient structural conditions for k-circulant graphs to be strongly r-robust with respect to a leader set. These conditions require a consecutive block of agents with enough leaders within it.
VIII. APPENDIX: k-CIRCULANT DIGRAPHS
- The appendix notes that its k-circulant robustness results were first presented in prior work.Source: §VIII · p. 8
- A circulant graph connects each node to offsets modulo n; undirected graphs use positive and negative offsets, while digraphs use positive offsets.Source: §VIII · p. 8
- A k-circulant digraph uses offsets 1 through k, and a k-circulant undirected graph uses offsets ±1 through ±k.Source: §VIII · p. 8
- A directed k-circulant graph is strongly r-robust with respect to L if it contains a consecutive block PL of size at most k with at least r members in L.Source: §VIII · p. 8
- The same consecutive-block condition establishes strong r-robustness for an undirected k-circulant graph.Source: §VIII · p. 8