On the fundamental limitations of performance for distributed decision-making in robotic networks
It addresses performance analysis for distributed algorithms in robotic networks, bridging computer science and controls, but is incremental in its theoretical contributions.
The paper studies fundamental performance limitations for distributed decision-making in robotic networks, covering problems like consensus and optimization, and presents bounds on time, message, and byte complexity to compare different approaches.
This paper studies fundamental limitations of performance for distributed decision-making in robotic networks. The class of decision-making problems we consider encompasses a number of prototypical problems such as average-based consensus as well as distributed optimization, leader election, majority voting, MAX, MIN, and logical formulas. We first propose a formal model for distributed computation on robotic networks that is based on the concept of I/O automata and is inspired by the Computer Science literature on distributed computing clusters. Then, we present a number of bounds on time, message, and byte complexity, which we use to discuss the relative performance of a number of approaches for distributed decision-making. From a methodological standpoint, our work sheds light on the relation between the tools developed by the Computer Science and Controls communities on the topic of distributed algorithms.