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. - STAMPA. - 48:(2016), pp. 290-312. [10.1002/rsa.20586]
Rumor spreading in random evolving graphs
CRESCENZI, PIERLUIGI;
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 in questo prodotto:
| File | Dimensione | Formato | |
|---|---|---|---|
|
RSA-2016.pdf
Accesso chiuso
Tipologia:
Pdf editoriale (Version of record)
Licenza:
Tutti i diritti riservati
Dimensione
186.23 kB
Formato
Adobe PDF
|
186.23 kB | Adobe PDF | Richiedi una copia |
I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
