Panagiotou, K.; Speidel, L.
(2017):
Asynchronous Rumor Spreading on Random Graphs.
In: Algorithmica, Vol. 78, No. 3: pp. 968989

Full text not available from 'Open Access LMU'.
Abstract
We perform a thorough study of various characteristics of the asynchronous pushpull protocol for spreading a rumor on ErdosRenyi random graphs G(n,p), for any p > c ln(n)/n with c > 1. In particular, we provide a simple strategy for analyzing the asynchronous pushpull protocol on arbitrary graph topologies and apply this strategy to Gn, p. We prove tight bounds of logarithmic order for the total time that is needed until the information has spread to all nodes. Surprisingly, the time required by the asynchronous pushpull protocol is asymptotically almost unaffected by the average degree of the graph. Similarly tight bounds for ErdosRenyi random graphs have previously only been obtained for the synchronous push protocol, where it has been observed that the total running time increases significantly for sparse random graphs. Finally, we quantify the robustness of the protocol with respect to transmission and node failures. Our analysis suggests that the asynchronous protocols are particularly robust with respect to these failures compared to their synchronous counterparts.