Abstract:A communication network is said to be "anonymous" if its agents are indistinguishable from each other; it is "dynamic" if its communication links may appear or disappear unpredictably over time. Assuming that each of the $n$ agents of an anonymous dynamic network is initially given an input, it takes $2\tau n$ communication rounds for the agents to compute an arbitrary (frequency-based) function of such inputs (Di Luna-Viglietta, DISC 2023), where $\tau$ is a parameter called "dynamic disconnectivity", and measures how far the network is from being always connected (for always connected dynamic networks, $\tau=1$).
It is known that, without making additional assumptions on the network and without knowing the number of agents $n$, it is impossible to compute most functions and explicitly terminate. In fact, current state-of-the-art algorithms only achieve stabilization, i.e., allow each agent to return an output after every communication round. Outputs can be changed, and are guaranteed to be all correct after $2\tau n$ rounds. Such algorithms rely on the incremental construction of a data structure called "history tree", which is augmented at every round. Thus, they end up consuming an unlimited amount of memory, and are also prone to errors in case of memory loss or corruption.
In this paper, we provide a general self-stabilizing algorithm for anonymous dynamic networks that stabilizes in $\max\{4\tau n-2\mu,2\mu\}$ rounds (where $\mu$ measures the amount of corrupted data initially present in the memory of each agent), as well as a general finite-state algorithm that stabilizes in $\tau(2n^2+n)$ rounds.
Our work improves upon previously known methods that only apply to static networks (Boldi-Vigna, Dist. Comp. 2002). In addition, we develop new fundamental techniques and operations involving history trees, which are of independent interest.
From: Giovanni Viglietta [view email]
[v1]
Sun, 1 Sep 2024 10:37:52 UTC (142 KB)
[v2]
Sun, 27 Oct 2024 10:19:31 UTC (142 KB)
[v3]
Sun, 24 Aug 2025 01:54:09 UTC (146 KB)
[v4]
Sat, 25 Jul 2026 19:52:54 UTC (147 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。