Skip to main content

2012 | OriginalPaper | Buchkapitel

Lower Bounds on Information Dissemination in Dynamic Networks

verfasst von : Bernhard Haeupler, Fabian Kuhn

Erschienen in: Distributed Computing

Verlag: Springer Berlin Heidelberg

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

We study lower bounds on information dissemination in adversarial dynamic networks. Initially,

k

pieces of information (henceforth called tokens) are distributed among

n

nodes. The tokens need to be broadcast to all nodes through a synchronous network in which the topology can change arbitrarily from round to round provided that some connectivity requirements are satisfied.

If the network is guaranteed to be connected in every round and each node can broadcast a single token per round to its neighbors, there is a simple token dissemination algorithm that manages to deliver all

k

tokens to all the nodes in

O

(

nk

) rounds. Interestingly, in a recent paper, Dutta et al. proved an almost matching Ω(

n

 + 

nk

/log

n

) lower bound for deterministic token-forwarding algorithms that are not allowed to combine, split, or change tokens in any way. In the present paper, we extend this bound in different ways.

If nodes are allowed to forward

b

 ≤ 

k

tokens instead of only one token in every round, a straight-forward extension of the

O

(

nk

) algorithm disseminates all

k

tokens in time

O

(

nk

/

b

). We show that for any randomized token-forwarding algorithm, Ω(

n

 + 

nk

/(

b

2

log

n

loglog

n

)) rounds are necessary. If nodes can only send a single token per round, but we are guaranteed that the network graph is

c

-vertex connected in every round, we show a lower bound of Ω(

nk

/(

c

log

3/2

n

)), which almost matches the currently best

O

(

nk

/

c

) upper bound. Further, if the network is

T

-interval connected, a notion that captures connection stability over time, we prove that Ω(

n

 + 

nk

/(

T

2

log

n

)) rounds are needed. The best known upper bound in this case manages to solve the problem in

O

(

n

 + 

nk

/

T

) rounds. Finally, we show that even if each node only needs to obtain a

δ

-fraction of all the tokens for some

δ

 ∈ [0,1], Ω(

nkδ

3

/log

n

) are still required.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Metadaten
Titel
Lower Bounds on Information Dissemination in Dynamic Networks
verfasst von
Bernhard Haeupler
Fabian Kuhn
Copyright-Jahr
2012
Verlag
Springer Berlin Heidelberg
DOI
https://doi.org/10.1007/978-3-642-33651-5_12