










Abstract:We introduce the problem of adaptive self-organization in which the nodes of an anonymous, synchronous dynamic network must distributively change the collective distribution of their responses (or "colors") as a function of time-varying environmental signals, even when these signals are only perceived locally and the network topology changes adversarially. Specifically, a signal adversary may change the type of signal and which node(s) witness that signal arbitrarily between rounds. If a signal (or lack thereof) $s$ persists in the system for sufficiently long, the dynamic network must stabilize such that nodes' colors closely approximate $r(s)$, a goal distribution defined by the problem instance. By symmetry, deterministic nodes can only hope to solve homogeneous instances of adaptive self-organization, i.e., those in which all nodes stabilize with the same color. We present a linear-time, logarithmic-memory, deterministic algorithm for this class of instances that works even when the multiplicity and location of signal witnesses change arbitrarily. We then give a randomized extension of this algorithm that solves arbitrary (i.e., not necessarily homogeneous) instances of adaptive self-organization with high probability in the same time and space bounds.
From: Joshua Daymude [view email]
[v1]
Wed, 29 Apr 2026 17:45:22 UTC (244 KB)
[v2]
Thu, 20 Aug 2026 04:39:24 UTC (131 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。