  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.
