Information Spreading in Dynamic Networks

Details Information Spreading in Dynamic Networks Information Spreading in Dynamic Networks

2011-12-02

arxiv.org/abs/1112.0384v1

Computer Science

Distributed, Parallel, and Cluster Computing

18 pages

Scientific paper

We study the fundamental problem of information spreading (also known as gossip) in dynamic networks. In gossip, or more generally, $k$-gossip, there are $k$ pieces of information (or tokens) that are initially present in some nodes and the problem is to disseminate the $k$ tokens to all nodes. The goal is to accomplish the task in as few rounds of distributed computation as possible. The problem is especially challenging in dynamic networks where the network topology can change from round to round and can be controlled by an on-line adversary. The focus of this paper is on the power of token-forwarding algorithms, which do not manipulate tokens in any way other than storing and forwarding them. We first consider a worst-case adversarial model first studied by Kuhn, Lynch, and Oshman~\cite{kuhn+lo:dynamic} in which the communication links for each round are chosen by an adversary, and nodes do not know who their neighbors for the current round are before they broadcast their messages. Our main result is an $\Omega(nk/\log n)$ lower bound on the number of rounds needed for any deterministic token-forwarding algorithm to solve $k$-gossip. This resolves an open problem raised in~\cite{kuhn+lo:dynamic}, improving their lower bound of $\Omega(n \log k)$, and matching their upper bound of $O(nk)$ to within a logarithmic factor. We next show that token-forwarding algorithms can achieve subquadratic time in the offline version of the problem where the adversary has to commit all the topology changes in advance at the beginning of the computation, and present two polynomial-time offline token-forwarding algorithms. Our results are a step towards understanding the power and limitation of token-forwarding algorithms in dynamic networks.

Affiliated with

Also associated with

No associations

Rating

Information Spreading in Dynamic Networks does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Information Spreading in Dynamic Networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Information Spreading in Dynamic Networks will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-139747