Asynchronous Rumor Spreading in Preferential Attachment Graphs

摘要

We show that the asynchronous push-pull protocol spreads rumors in preferential attachment graphs (as denned by Barabasi and Albert) in time O(√log n) to all but a lower order fraction of the nodes with high probability. This is significantly faster than what synchronized protocols can achieve; an obvious lower bound for these is the average distance, which is known to be θ(log n/ log log n).