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
CRESCENZI, PIERLUIGI;
2016-01-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:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
