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 Tools annual

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 Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

We focus on the well-studied problem of distributed overlay networkconstruction. We consider a synchronous gossip-based communication model wherein each round a node can send a message of small size to another node whoseidentifier it knows. The network is assumed to be reconfigurable, i.e., a nodecan add new connections (edges) to other nodes whose identifier it knows ordrop existing connections. Each node initially has only knowledge of its ownidentifier and the identifiers of its neighbors. The overlay constructionproblem is, given an arbitrary (connected) graph, to reconfigure it to obtain abounded-degree expander graph as efficiently as possible. The overlayconstruction problem is relevant to building real-world peer-to-peer networktopologies that have desirable properties such as low diameter, highconductance, robustness to adversarial deletions, etc.  Our main result is that we show that starting from any arbitrary (connected)graph $G$ on $n$ nodes and $m$ edges, we can construct an overlay network thatis a constant-degree expander in polylog $n$ rounds using only $\tilde{O}(n)$messages. Our time and message bounds are both essentially optimal (up topolylogarithmic factors). Our distributed overlay construction protocol is verylightweight as it uses gossip (each node communicates with only one neighbor ineach round) and also scalable as it uses only $\tilde{O}(n)$ messages, which issublinear in $m$ (even when $m$ is moderately dense). To the best of ourknowledge, this is the first result that achieves overlay network constructionin polylog $n$ rounds and $o(m)$ messages. Our protocol uses graph sketches ina novel way to construct an expander overlay that is both time andcommunication efficient. A consequence of our overlay construction protocol isthat distributed computation can be performed very efficiently in this model.

Time- and Communication-Efficient Overlay Network Construction via Gossip