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.
Clementi, A., Crescenzi, P., Doerr, C., Fraigniaud, P., Pasquale, F., Silvestri, R. (2016). Rumor spreading in random evolving graphs. RANDOM STRUCTURES & ALGORITHMS, 48(2), 290-312 [10.1002/rsa.20586].
Rumor spreading in random evolving graphs
CLEMENTI, ANDREA;PASQUALE, FRANCESCO;
2016-03-01
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 | |
|---|---|---|---|
|
10.1002_rsa.20586.pdf
solo utenti autorizzati
Licenza:
Copyright dell'editore
Dimensione
191.59 kB
Formato
Adobe PDF
|
191.59 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
