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 address the problem of building and maintaining distributed spanning treesin highly dynamic networks, in which topological events can occur at any timeand any rate, and no stable periods can be assumed. In these harshenvironments, we strive to preserve some properties such as cycle-freeness orthe existence of a root in each tree, in order to make it possible to keepusing the trees uninterruptedly (to a possible extent). Our algorithm operatesat a coarse-grain level, using atomic pairwise interactions in a way akin torecent population protocol models. The algorithm relies on a perpetualalternation of \emph{topology-induced splittings} and \emph{computation-inducedmergings} of a forest of spanning trees. Each tree in the forest hosts exactlyone token (also called root) that performs a random walk {\em inside} the tree,switching parent-child relationships as it crosses edges. When two tokens arelocated on both sides of a same edge, their trees are merged upon this edge andone token disappears. Whenever an edge that belongs to a tree disappears, itschild endpoint regenerates a new token instantly. The main features of thisapproach is that both \emph{merging} and \emph{splitting} are purely localizedphenomenons. In this paper, we present and motivate the algorithm, and we proveits correctness in arbitrary dynamic networks. Then we discuss severalimplementation choices around this general principle. Preliminary resultsregarding its analysis are also discussed, in particular an analyticalexpression of the expected merging time for two given trees in a staticcontext.

Distributed Maintenance of Anytime Available Spanning Trees in Dynamic Networks