On the Average Communication Complexity of Asynchronous Distributed Algorithms

We study the communication complexity of asynchronous distributed algorithms, such as the dis-tributed Bellman-Ford algorithm for the shortest path problem. Such algorithms can generate excessively many messages in the worst case. Nevertheless, we show that, under certain proba-bilistic assumptions, the expected number of messages generated per time unit is bounded by a polynomial function of the number of processors under a very general model of distributed com-putation. Furthermore, for constant-degree processor graphs, the expected number of generated messages is only O(nT), where n is the number of processors and T is the running time. We also argue that our bounds are tight in certain cases. We conclude that (under our model) any asyn-chronous algorithm with good time complexity will also have good communication complexity, on the average