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 use network coding to improve the speed of distributed computation in thedynamic network model of Kuhn, Lynch and Oshman [STOC '10]. In this model anadversary adaptively chooses a new network topology in every round, making evenbasic distributed computations challenging.  Kuhn et al. show that n nodes, each starting with a d-bit token, canbroadcast them to all nodes in time O(n^2) using b-bit messages, where b > d +log n. Their algorithms take the natural approach of {token forwarding}: inevery round each node broadcasts some particular token it knows. They provematching Omega(n^2) lower bounds for a natural class of token forwardingalgorithms and an Omega(n log n) lower bound that applies to alltoken-forwarding algorithms.  We use network coding, transmitting random linear combinations of tokens, tobreak both lower bounds. Our algorithm's performance is quadratic in themessage size b, broadcasting the n tokens in roughly d/b^2 * n^2 rounds. For b= d = O(log n) our algorithms use O(n^2/log n) rounds, breaking the first lowerbound, while for larger message sizes we obtain linear-time algorithms. We alsoconsider networks that change only every T rounds, and achieve an additionalfactor T^2 speedup. This contrasts with related lower and upper bounds of Kuhnet al. implying that for natural token-forwarding algorithms a speedup of T,but not more, can be obtained. Lastly, we give a general way to derandomizerandom linear network coding, that also leads to new deterministic informationdissemination algorithms.

Faster Information Dissemination in Dynamic Networks via Network Coding