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

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.
Pubblicato
Rilevanza internazionale
Articolo
Esperti anonimi
Settore INF/01 - Informatica
English
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].
Clementi, A; Crescenzi, P; Doerr, C; Fraigniaud, P; Pasquale, F; Silvestri, R
Articolo su rivista
File in questo prodotto:
File Dimensione Formato  
10.1002_rsa.20586.pdf

accesso solo dalla rete interna

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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2108/181306
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 16
  • ???jsp.display-item.citation.isi??? 15
social impact