Computer Science – Discrete Mathematics
Scientific paper
2011-04-14
Computer Science
Discrete Mathematics
Scientific paper
In this paper, we study the question of how efficiently a collection of interconnected nodes can perform a global computation in the widely studied GOSSIP model of communication. In this model, nodes do not know the global topology of the network, and they may only initiate contact with a single neighbor in each round. This model contrasts with the much less restrictive LOCAL model, where a node may simultaneously communicate with all of its neighbors in a single round. A basic question in this setting is how many rounds of communication are required for the information dissemination problem, in which each node has some piece of information and is required to collect all others. In this paper, we give an algorithm that solves the information dissemination problem in at most $O(D+\text{polylog}{(n)})$ rounds in a network of diameter $D$, withno dependence on the conductance. This is at most an additive polylogarithmic factor from the trivial lower bound of $D$, which applies even in the LOCAL model. In fact, we prove that something stronger is true: any algorithm that requires $T$ rounds in the LOCAL model can be simulated in $O(T +\mathrm{polylog}(n))$ rounds in the GOSSIP model. We thus prove that these two models of distributed computation are essentially equivalent.
Censor-Hillel Keren
Haeupler Bernhard
Kelner Jonathan A.
Maymounkov Petar
No associations
LandOfFree
Global Computation in a Poorly Connected World: Fast Rumor Spreading with No Dependence on Conductance 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 Global Computation in a Poorly Connected World: Fast Rumor Spreading with No Dependence on Conductance, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Global Computation in a Poorly Connected World: Fast Rumor Spreading with No Dependence on Conductance will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-8099