2012/08/14 by Vincent Gripon, Gripon, Vincent, Vitaly Skachek +3
Computer Science · #Cooperative Communication and Network Coding #Data Structures and Algorithms (cs.DS) #Distributed #FOS: Computer and information sciences #Mobile Ad Hoc Networks #Opportunistic and Delay-Tolerant Networks #Parallel #and Cluster Computing (cs.DC) #cs.DC #cs.DS
paper · pdf · doi:10.48550/arxiv.1208.2936
16 pages
arxiv created 2012/08/14 · openalex publication_date 2012/08/14 · arxiv updated 2012/08/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study a gossip protocol called forwarding without repeating (FWR). The objective is to spread multiple rumors over a graph as efficiently as possible. FWR accomplishes this by having nodes record which messages they have forwarded to each neighbor, so that each message is forwarded at most once to each neighbor. We prove that FWR spreads a rumor over a strongly connected digraph, with high probability, in time which is within a constant factor of optimal for digraphs with bounded out-degree. Moreover, on digraphs with bounded out-degree and bounded number of rumors, the number of transmissions required by FWR is arbitrarily better than that of existing approaches. Specifically, FWR requires O(n) messages on bounded-degree graphs with n nodes, whereas classical forwarding and an approach based on network coding both require ω(n) messages. Our results are obtained using combinatorial and probabilistic arguments. Notably, they do not depend on expansion properties of the underlying graph, and consequently the message complexity of FWR is arbitrarily better than classical forwarding even on constant-degree expander graphs, as n → ∞. In resource-constrained applications, where each transmission consumes battery power and bandwidth, our results suggest that using a small amount of memory at each node leads to a significant savings.