The paper “Scalability and Fragility in Bounded-Degree Consensus Networks” by myself, Rick Middleton and Maria Seron just got accepted to the 8th IFAC Workshop on Distributed Estimation and Control in Networked Systems (NecSys).
Here, we discuss the fact that consensus algorithms (of various orders) tend to lack scalability in networks where each node has a bounded degree. For example, convergence rates, sensitivity, and, in the case of high-order consensus, stability properties, tend to deteriorate as the network grows. This is because the algebraic connectivity decreases with network size in most graph families.
This can only be avoided in expander families, where the algebraic connectivity, and thus performance properties, can be maintained as the network grows. However, consensus over such networks is very fragile towards a grounding of the network. If an expander network becomes grounded, for example, if one agent disconnects from its neighbors and begins acting as a leader, the performance of a large network may deteriorate by orders of magnitude. In high-order consensus, stability can be lost, as shown in the figure accompanying this post.
This work is part of my overall research effort in describing fundamental limitations and fragilities related to the scalability of distributed control algorithms.
Emma Tegling 