Faster Rumor Spreading: Breaking the log n Barrier

Chen Avin and Robert Elsässer

Abstract. rounds has been a well known upper bound for rumor spreading using push&pull in the random phone call model (i.e., uniform gossip in the complete graph). A matching lower bound of is also known for this special case. Under the assumptions of this model and with a natural addition that nodes can call a partner once they learn its address (e.g., its IP address) we present a new distributed, address-oblivious and robust algorithm that uses push&pull with pointer jumping to spread a rumor to all nodes in only rounds, w.h.p. This algorithm can also cope with node failures, in which case all but nodes become informed within rounds, w.h.p.

Guest: Chen Avin

Host: Shantanu Das

Leave a Reply

Your email address will not be published.

165,577 Spam Comments Blocked so far by Spam Free Wordpress

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>