Markovian evolving graphs [2] are dynamic-graph models where the links among a fixed set of nodes change during time according to an arbitrary Markovian rule. They are extremely general and they can well describe important dynamic-network scenarios. We study the speed of information spreading in the stationaryphase by analyzing the completion time of the flooding mechanism. We prove a general theorem that establishes an upper bound on flooding time in any stationary Markovian evolving graph in terms of its node-expansion properties. We apply our theorem in two natural and relevant cases of such dynamic graphs: edge-Markovian evolving graphs [24, 7] where the probability of existence of any edge at time t depends on the existence (or not) of the same edge at time t-1; geometric Markovian evolving graphs [4, 10, 9] where the Markovian behaviour is yielded by n mobile radio stations, with fixed transmission radius, that perform n independent random walks over a square region of the plane. In both cases, the obtained upper bounds are shown to be nearly tight and, in fact, they turn out to betight for a large range of the values of the input parameters. © 2009 IEEE.

Clementi, A., Monti, A., Pasquale, F., Silvestri, R. (2009). Information spreading in stationary markovian evolving graphs. In IPDPS 2009 - Proceedings of the 2009 IEEE International Parallel and Distributed Processing Symposium (pp.1-12) [10.1109/IPDPS.2009.5160986].

Information spreading in stationary markovian evolving graphs

Pasquale, Francesco;
2009-01-01

Abstract

Markovian evolving graphs [2] are dynamic-graph models where the links among a fixed set of nodes change during time according to an arbitrary Markovian rule. They are extremely general and they can well describe important dynamic-network scenarios. We study the speed of information spreading in the stationaryphase by analyzing the completion time of the flooding mechanism. We prove a general theorem that establishes an upper bound on flooding time in any stationary Markovian evolving graph in terms of its node-expansion properties. We apply our theorem in two natural and relevant cases of such dynamic graphs: edge-Markovian evolving graphs [24, 7] where the probability of existence of any edge at time t depends on the existence (or not) of the same edge at time t-1; geometric Markovian evolving graphs [4, 10, 9] where the Markovian behaviour is yielded by n mobile radio stations, with fixed transmission radius, that perform n independent random walks over a square region of the plane. In both cases, the obtained upper bounds are shown to be nearly tight and, in fact, they turn out to betight for a large range of the values of the input parameters. © 2009 IEEE.
23rd IEEE International Parallel and Distributed Processing Symposium, IPDPS 2009
Rome, ita
2009
IEEE Computer Society Technical Committee on Parallel Processing
Rilevanza internazionale
2009
Settore INF/01 - INFORMATICA
English
Computational Theory and Mathematics; Hardware and Architecture; Software
Intervento a convegno
Clementi, A., Monti, A., Pasquale, F., Silvestri, R. (2009). Information spreading in stationary markovian evolving graphs. In IPDPS 2009 - Proceedings of the 2009 IEEE International Parallel and Distributed Processing Symposium (pp.1-12) [10.1109/IPDPS.2009.5160986].
Clementi, Aef; Monti, A; Pasquale, F; Silvestri, R
File in questo prodotto:
File Dimensione Formato  
cmps_ipdps09.pdf

solo utenti autorizzati

Licenza: Copyright dell'editore
Dimensione 308.89 kB
Formato Adobe PDF
308.89 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/196239
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 46
  • ???jsp.display-item.citation.isi??? 15
social impact