We show that if a connected graph with n nodes has conductance φ then rumour spreading, also known as randomized broadcast, successfully broadcasts a message within Õ(φ-1·log n), many rounds with high probability, regardless of the source, by using the PUSH-PULL strategy. The Õ(⋯) notation hides a polylog φ-1 factor. This result is almost tight since there exists graph of n nodes, and conductance φ, with diameter Ω(φ-1·log n). If, in addition, the network satisfies some kind of uniformity condition on the degrees, our analysis implies that both both PUSH and PULL, by themselves, successfully broadcast the message to every node in the same number of rounds. © 2010 ACM.
Almost tight bounds for rumour spreading with conductance / Chierichetti, Flavio; Silvio, Lattanzi; Panconesi, Alessandro. - (2010), pp. 399-407. (Intervento presentato al convegno ACM Symposium on Theory of Computing, (STOC 2010) tenutosi a Cambridge; United States nel June 6-8, 2010) [10.1145/1806689.1806745].
Almost tight bounds for rumour spreading with conductance
CHIERICHETTI, FLAVIO;PANCONESI, Alessandro
2010
Abstract
We show that if a connected graph with n nodes has conductance φ then rumour spreading, also known as randomized broadcast, successfully broadcasts a message within Õ(φ-1·log n), many rounds with high probability, regardless of the source, by using the PUSH-PULL strategy. The Õ(⋯) notation hides a polylog φ-1 factor. This result is almost tight since there exists graph of n nodes, and conductance φ, with diameter Ω(φ-1·log n). If, in addition, the network satisfies some kind of uniformity condition on the degrees, our analysis implies that both both PUSH and PULL, by themselves, successfully broadcast the message to every node in the same number of rounds. © 2010 ACM.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
