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

Self-stabilizing protocols enable distributed systems to recover correctbehavior starting from any arbitrary configuration. In particular, whenprocessors communicate by message passing, fake messages may be placed incommunication links by an adversary. When the number of such fake messages isunknown, self-stabilization may require huge resources: (a) generic solutions(a.k.a. data link protocols) require unbounded resources, which makes themunrealistic to deploy and (b) specific solutions (e.g., census or treeconstruction) require $O(n\log n)$ or $O(\Delta\log n)$ bits of memory pernode, where $n$ denotes the network size and $\Delta$ its maximum degree, whichmay prevent scalability.  We investigate the possibility of resource efficient self-stabilizingprotocols in this context. Specifically, we present a self-stabilizing protocolfor $(\Delta+1)$-coloring in any n-node graph, under the asynchronousmessage-passing model. It is deterministic, it converges in $O(k\Delta n^2\logn)$ message exchanges, where $k$ is the bound of the link capacity in terms ofnumber of messages, and it uses messages on $O(\log\log n+\log\Delta)$ bitswith a memory of $O(\Delta\log\Delta+\log\log n)$ bits at each node. Theresource consumption of our protocol is thus almost oblivious to the number ofnodes, enabling scalability. Moreover, a striking property of our protocol isthat the nodes do not need to know the number, or any bound on the number ofmessages initially present in each communication link of the initial(potentially corrupted) network configuration. This permits our protocol tohandle any future network with unknown message capacity communication links. Akey building block of our coloring scheme is a spanning directed acyclic graphconstruction, that is of independent interest, and can serve as a useful toolfor solving other tasks in this challenging setting.

Ressource Efficient Stabilization for Local Tasks despite Unknown Capacity Links