Distributed consensus with mixed time/communication bandwidth performance metrics
For designers of dense robotic networks using wireless communication, this work provides theoretical bounds and practical algorithms to optimize bandwidth usage in consensus problems.
This paper studies the trade-off between time and communication bandwidth in distributed consensus, proving a lower bound on bandwidth complexity and presenting a bandwidth-optimal algorithm for a wide class of consensus functions. It also introduces a tunable algorithm that allows trading communication complexity for time complexity, with favorable worst-case bandwidth compared to known algorithms.
In this paper we study the inherent trade-off between time and communication complexity for the distributed consensus problem. In our model, communication complexity is measured as the maximum data throughput (in bits per second) sent through the network at a given instant. Such a notion of communication complexity, referred to as bandwidth complexity, is related to the frequency bandwidth a designer should collectively allocate to the agents if they were to communicate via a wireless channel, which represents an important constraint for dense robotic networks. We prove a lower bound on the bandwidth complexity of the consensus problem and provide a consensus algorithm that is bandwidth-optimal for a wide class of consensus functions. We then propose a distributed algorithm that can trade communication complexity versus time complexity as a function of a tunable parameter, which can be adjusted by a system designer as a function of the properties of the wireless communication channel. We rigorously characterize the tunable algorithm's worst-case bandwidth complexity and show that it compares favorably with the bandwidth complexity of well-known consensus algorithm.