Convergence Time Distributions for Max-Consensus over Unreliable Networks
For designers of multi-agent systems operating over unreliable networks, this work provides a deterministic method to obtain convergence time distributions, enabling reliability guarantees without simulation.
The paper introduces LiFE-CD, an algorithm that computes the full probability distribution of convergence time for max-consensus in multi-agent systems with Bernoulli link failures, enabling deadline-aware protocol design. It achieves exact results for acyclic networks and tight upper bounds for cyclic networks, with lower computational cost than Monte Carlo simulations.
This paper proposes the LiFE-CD algorithm for convergence time analysis of the max-consensus algorithm in multi-agent systems under Bernoulli-distributed link failures. Unlike existing approaches, which either assume ideal communication or provide asymptotic upper bounds on the expected convergence time, LiFE-CD deterministically computes the full probability distribution of the convergence time from network topology and individual link failure probabilities, without simulation. The full probability distribution enables deadline-aware protocol design with specified reliability guarantees. Based on geometrically distributed link delays, the proposed algorithm iteratively reduces the given network topology considering both unicast and broadcast transmissions. LiFE-CD yields exact results for acyclic networks and, for cyclic networks, tight upper bounds on the convergence time via shortest-path spanning tree construction. Numerical results confirm analytical exactness for acyclic networks, validate tightness for cyclic networks, and demonstrate improvement over existing approaches. Our complexity analysis shows reduced computational cost compared to Monte Carlo simulations, while eliminating stochastic variability and enhancing reproducibility. All results extend directly to min-consensus by structural equivalence.