Fundamental Performance Limitations for Average Consensus in Open Multi-Agent Systems
share
We derive fundamental performance limitations for intrinsic average consensus problems in open multi-agent systems, which are systems subject to frequent arrivals and departures of agents. Each agent holds a value, and the objective of the agents is to collaboratively estimate the average of the values of the agents presently in the system. Algorithms solving such problems in open systems are poised to never converge because of the permanent variations in the composition, size and objective pursued by the agents of the system. We provide lower bounds on the expected Mean Square Error of averaging algorithms in open systems of fixed size. Our derivation is based on the analysis of an algorithm that achieves optimal performance on some model of communication within the system. We obtain a generic bound that depends on the properties of such communication schemes, and instantiate that result for all-to-one and one-to-one communication models. A comparison between those bounds and algorithms implementable with those models is then provided to highlight their validity.
READ FULL TEXT