We analyze randomized broadcast in dynamic networks modeled as edge-Markovian evolving graphs. The most realistic range of edge-Markovian parameters yields sparse and disconnected graphs. We prove that, in this setting, the “push” protocol completes with high probability in optimal logarithmic time.
Rumor spreading in random evolving graphs / Clementi, Andrea; Crescenzi, Pierluigi; Doerr, Carola; Fraigniaud, Pierre; Pasquale, Francesco; Silvestri, Riccardo. - In: RANDOM STRUCTURES & ALGORITHMS. - ISSN 1042-9832. - 48:2(2016), pp. 290-312. [10.1002/rsa.20586]
Rumor spreading in random evolving graphs
SILVESTRI, RICCARDO
2016
Abstract
We analyze randomized broadcast in dynamic networks modeled as edge-Markovian evolving graphs. The most realistic range of edge-Markovian parameters yields sparse and disconnected graphs. We prove that, in this setting, the “push” protocol completes with high probability in optimal logarithmic time.File allegati a questo prodotto
| File | Dimensione | Formato | |
|---|---|---|---|
|
Silvestri_rumor_2016.pdf
solo gestori archivio
Tipologia:
Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
191.59 kB
Formato
Adobe PDF
|
191.59 kB | Adobe PDF | Contatta l'autore |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
