Search papers, labs, and topics across Lattice.
This paper introduces the problem of adaptive self-organization in dynamic networks, where nodes must adjust their "color" distribution based on local, time-varying signals under adversarial network topology changes. The authors prove deterministic solutions are limited to homogeneous goal distributions and present a linear-time, logarithmic-memory algorithm for this case, which can be strengthened with knowledge of network size. They then provide a randomized algorithm that solves arbitrary instances of the problem with high probability when nodes know the goal distributions.
Even with adversarial network changes and only local signals, surprisingly simple distributed algorithms can enable dynamic networks to self-organize and adapt to changing environmental goals.
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 reach and remain in a distribution closely approximating $r(s)$, a goal distribution defined by the problem instance. We first prove that if nodes are deterministic, the only solvable instances of adaptive-self organization are those with homogeneous goal distributions, i.e., those where all nodes must stabilize with the same color. We then present a linear-time, logarithmic-memory, deterministic algorithm for this subclass of instances that works even when the multiplicity and location of signal witnesses change arbitrarily. When nodes know $n$, the number of nodes in the network, a small adaptation of this algorithm achieves a stronger convergence property in which adversarial edge and signal dynamics are entirely unable to disturb stabilized configurations. Finally, we present a randomized extension of these algorithms that solves arbitrary (i.e., not necessarily homogeneous) instances of adaptive self-organization with high probability when nodes know the goal distributions.
