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 the problem of randomized information dissemination in networks. Wecompare the now standard PUSH-PULL protocol, with agent-based alternativeswhere information is disseminated by a collection of agents performingindependent random walks. In the VISIT-EXCHANGE protocol, both nodes and agentsstore information, and each time an agent visits a node, the two exchange allthe information they have. In the MEET-EXCHANGE protocol, only the agents storeinformation, and exchange their information with each agent they meet.  We consider the broadcast time of a single piece of information in an$n$-node graph for the above three protocols, assuming a linear number ofagents that start from the stationary distribution. We observe that there aregraphs on which the agent-based protocols are significantly faster thanPUSH-PULL, and graphs where the converse is true. We attribute the goodperformance of agent-based algorithms to their inherently fair bandwidthutilization, and conclude that, in certain settings, agent-based informationdissemination, separately or in combination with PUSH-PULL, can significantlyimprove the broadcast time.  The graphs considered above are highly non-regular. Our main technical resultis that on any regular graph of at least logarithmic degree, PUSH-PULL andVISIT-EXCHANGE have the same asymptotic broadcast time. The proof uses a novelcoupling argument which relates the random choices of vertices in PUSH-PULLwith the random walks in VISIT-EXCHANGE. Further, we show that the broadcasttime of MEET-EXCHANGE is asymptotically at least as large as the other two's onall regular graphs, and strictly larger on some regular graphs.  As far as we know, this is the first systematic and thorough comparison ofthe running times of these very natural information dissemination protocols.

How to Spread a Rumor: Call Your Neighbors or Take a Walk?