2015/12/08 by Chen Avin, Avin, Chen, Robert Elsässer⋆ +1 · 1 citation
Computer Science · #Algorithms and Data Compression #Caching and Content Delivery #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Opportunistic and Delay-Tolerant Networks
paper · pdf · doi:10.48550/arxiv.1512.03022
openalex publication_date 2015/12/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
O(log n) 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 Ω(log n) is also known for this special case. Under the assumption 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 O(√(log n)) rounds, w.h.p. This algorithm can also cope with F= O(n/2√(log n)) node failures, in which case all but O(F) nodes become informed within O(√(log n)) rounds, w.h.p.