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

In this paper, we study the question of how efficiently a collection ofinterconnected nodes can perform a global computation in the widely studiedGOSSIP model of communication. In this model, nodes do not know the globaltopology of the network, and they may only initiate contact with a singleneighbor in each round. This model contrasts with the much less restrictiveLOCAL model, where a node may simultaneously communicate with all of itsneighbors in a single round. A basic question in this setting is how manyrounds of communication are required for the information dissemination problem,in which each node has some piece of information and is required to collect allothers. In this paper, we give an algorithm that solves the informationdissemination problem in at most $O(D+\text{polylog}{(n)})$ rounds in a networkof diameter $D$, withno dependence on the conductance. This is at most anadditive polylogarithmic factor from the trivial lower bound of $D$, whichapplies even in the LOCAL model. In fact, we prove that something stronger istrue: any algorithm that requires $T$ rounds in the LOCAL model can besimulated in $O(T +\mathrm{polylog}(n))$ rounds in the GOSSIP model. We thusprove that these two models of distributed computation are essentiallyequivalent.

Global Computation in a Poorly Connected World: Fast Rumor Spreading with No Dependence on Conductance