Technical Report No. 281 - Abstract

Mohamad Ahmadi, Fabian Kuhn, Shay Kutten, Anisur Rahaman Molla and Gopal Pandurangan
The Communication Cost of Information Spreading in Dynamic Networks

This paper investigates the message complexity of distributed information spreading (a.k.a gossip or token dissemination) in adversarial dynamic networks. While distributed computations in dynamic networks have been studied intensively over the last years, almost all of the existing work solely focuses on the time complexity of distributed algorithms.

In information spreading, the goal is to spread k tokens of information to every node on an n-node network. We consider the amortized (average) message complexity of spreading a token, assuming that the number of tokens is large. In a static network, this basic problem can be solved using (asymptotically optimal) O(n) amortized messages per token. Our focus is on token-forwarding algorithms, which do not manipulate tokens in any way other than storing, copying, and forwarding them.

We assume that the dynamic sequence of network graphs is provided by an adaptive worst-case adversary that is aware of the status of all nodes and the algorithm (including the current random choices) and can rewire the network arbitrarily in every round with the constraint that it always keeps the n-node network connected. We present two sets of results depending on how nodes send messages to their neighbors:

1. Local broadcast setting: We show a tight lower bound of Ω(n^2) on the number of amortized local broadcasts, which is matched by the naive flooding algorithm.
2. Unicast: We study the message complexity as a function of the number of dynamic changes in the network. To facilitate this, we introduce a natural complexity measure for analyzing dynamic networks called adversary-competitive message complexity where the adversary pays a unit cost for every topological change. Under this model, it is shown that if k is sufficiently large, we can obtain an optimal amortized message complexity of O(n). We also present a randomized algorithm that achieves subquadratic amortized message complexity when the number of tokens is not large under an oblivious adversary, which is a worst-case adversary that is oblivious to the random choices made by the algorithm. Our analysis of the unicast communication under the adversary-competitive model (which may be of independent interest) is a main contribution of this paper.