Information Spreading in Dynamic Networks under Oblivious Adversaries
Preprint
Abstract
We study the problem of gossip in dynamic networks controlled by an adversary that can modify the network arbitrarily from one round to another, provided that the network is always connected. In the gossip problem, $n$ tokens are arbitrarily distributed among the $n$ network nodes, and the goal is to disseminate all the $n$ tokens to every node. Our focus is on token-forwarding algorithms, which do not manipulate tokens in any way other than storing, copying, and forwarding them. Gossip can be completed in linear time in any static network, but a basic open question for dynamic networks is the existence of a distributed protocol that can do significantly better than an easily achievable bound of $O(n^2)$ rounds. In previous work, it has been shown that under adaptive adversaries, every token forwarding algorithm requires $\Omega(n^2/\log n)$ rounds. In this paper, we study oblivious adversaries, which differ from adaptive adversaries in one crucial aspect--- they are oblivious to random choices made by the protocol. We present an $\tilde{\Omega}(n^{3/2})$ lower bound under an oblivious adversary for RANDDIFF, a natural algorithm in which neighbors exchange a token chosen uniformly at random from the difference of their token sets. We also present an $\tilde{\Omega}(n^{4/3})$ bound under a stronger notion of oblivious adversary for symmetric knowledge-based algorithms. On the positive side, we present a centralized algorithm that completes gossip in $\tilde{O}(n^{3/2})$ rounds. We also show an $\tilde{O}(n^{5/3})$ upper bound for RANDDIFF in a restricted class of oblivious adversaries, which we call paths-respecting.
Keywords
All Related Versions
This publication has 14 references indexed in Scilit:
- Enabling Robust and Efficient Distributed Computation in Dynamic Peer-to-Peer Networks2015
- Parsimonious flooding in dynamic graphsDistributed Computing, 2011
- Broadcasting in dynamic radio networksJournal of Computer and System Sciences, 2009
- Geographic routing in social networksProceedings of the National Academy of Sciences, 2005
- Building a reference combinatorial model for MANETsIEEE Network, 2004
- The Diameter of a Scale-Free Random GraphCombinatorica, 2004
- Crawling on Simple Models of Web GraphsInternet Mathematics, 2004
- Connectivity and Inference Problems for Temporal NetworksJournal of Computer and System Sciences, 2002
- Graph structure in the WebComputer Networks, 2000
- Concurrent Broadcast for Information DisseminationIEEE Transactions on Software Engineering, 1985