On the fundamental limitations of performance for distributed decision-making in robotic networks
Federico Rossi, Marco Pavone · 2014
This paper studies formal models and 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 evaluation of logical formulas. Specifically, we first propose a formal model 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 investigate the relative performance of a number of algorithmic 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 computation.