English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We study a gossip protocol called forwarding without repeating (FWR). Theobjective is to spread multiple rumors over a graph as efficiently as possible.FWR accomplishes this by having nodes record which messages they have forwardedto each neighbor, so that each message is forwarded at most once to eachneighbor. 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 fordigraphs with bounded out-degree. Moreover, on digraphs with bounded out-degreeand bounded number of rumors, the number of transmissions required by FWR isarbitrarily better than that of existing approaches. Specifically, FWR requiresO(n) messages on bounded-degree graphs with n nodes, whereas classicalforwarding and an approach based on network coding both require {\omega}(n)messages. Our results are obtained using combinatorial and probabilisticarguments. Notably, they do not depend on expansion properties of theunderlying graph, and consequently the message complexity of FWR is arbitrarilybetter than classical forwarding even on constant-degree expander graphs, as n\rightarrow \infty. In resource-constrained applications, where eachtransmission consumes battery power and bandwidth, our results suggest thatusing a small amount of memory at each node leads to a significant savings.

Forwarding Without Repeating: Efficient Rumor Spreading in Bounded-Degree Graphs