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 consider deterministic distributed algorithms for reaching agreement insynchronous networks of arbitrary topologies. Links are bi-directional andprone to failures while nodes stay non-faulty at all times. A faulty link mayomit messages. Agreement among nodes is understood as holding in each connectedcomponent of a network obtained by removing faulty links. We call``disconnected agreement'' the algorithmic problem of reaching such agreement.We introduce the concept of stretch, which is the number of connectedcomponents of a network, obtained by removing faulty links, minus~$1$ plus thesum of diameters of connected components. We define the concepts of ``fast''and ``early-stopping'' algorithms for disconnected agreement by referring tostretch. A network has $n$ nodes and $m$ links. Nodes are normally assumed toknow their own names and ability to associate communication with local ports.If we additionally assume that a bound~$\Lambda$ on stretch is known to allnodes, then there is an algorithm for disconnected agreement working in time$O(\Lambda)$ using messages of $O(\log n)$ bits. We give a general disconnectedagreement algorithm operating in~$n+1$ rounds that uses messages of $O(\log n)$bits. Let~$\lambda$ be an unknown stretch occurring in an execution; we give analgorithm working in time~$(\lambda+2)^3$ and using messages of $O(n\log n)$bits. We show that disconnected agreement can be solved in the optimal$O(\lambda)$ time, but at the cost of increasing message size to~$O(m\log n)$.We also design an algorithm that uses only~$O(n)$ non-faulty links and works intime~$O(n m)$, while nodes start with their ports mapped to neighbors andmessages carry $O(m\log n)$ bits. We prove lower bounds on the performance ofdisconnected-agreement solutions that refer to the parameters of evolvingnetwork topologies and the knowledge available to nodes.

Disconnected Agreement in Networks Prone to Link Failures