DROPS

Document

Brief Announcement

DOI: 10.4230/LIPIcs.SAND.2026.27

Brief Announcement: Adaptive Self-Organization in Anonymous Dynamic Networks

Authors: Garrett Parzych and Joshua J. Daymude

Published in: LIPIcs, Volume 373, 5th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2026)

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 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.

Cite as

Garrett Parzych and Joshua J. Daymude. Brief Announcement: Adaptive Self-Organization in Anonymous Dynamic Networks. In 5th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 373, pp. 27:1-27:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{parzych_et_al:LIPIcs.SAND.2026.27,
  author =	{Parzych, Garrett and Daymude, Joshua J.},
  title =	{{Brief Announcement: Adaptive Self-Organization in Anonymous Dynamic Networks}},
  booktitle =	{5th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2026)},
  pages =	{27:1--27:6},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-427-7},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{373},
  editor =	{Mertzios, George B. and Richa, Andr\'{e}a W.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2026.27},
  URN =		{urn:nbn:de:0030-drops-262610},
  doi =		{10.4230/LIPIcs.SAND.2026.27},
  annote =	{Keywords: Dynamic networks, anonymous nodes, broadcast, self-organization, biological distributed algorithms}
}

Document

DOI: 10.4230/LIPIcs.DISC.2024.35

Memory Lower Bounds and Impossibility Results for Anonymous Dynamic Broadcast

Authors: Garrett Parzych and Joshua J. Daymude

Published in: LIPIcs, Volume 319, 38th International Symposium on Distributed Computing (DISC 2024)

Abstract

Broadcast is a ubiquitous distributed computing problem that underpins many other system tasks. In static, connected networks, it was recently shown that broadcast is solvable without any node memory and only constant-size messages in worst-case asymptotically optimal time (Hussak and Trehan, PODC'19/STACS'20/DC'23). In the dynamic setting of adversarial topology changes, however, existing algorithms rely on identifiers, port labels, or polynomial memory to solve broadcast and compute functions over node inputs. We investigate space-efficient, terminating broadcast algorithms for anonymous, synchronous, 1-interval connected dynamic networks and introduce the first memory lower bounds in this setting. Specifically, we prove that broadcast with termination detection is impossible for idle-start algorithms (where only the broadcaster can initially send messages) and otherwise requires Ω(log n) memory per node, where n is the number of nodes in the network. Even if the termination condition is relaxed to stabilizing termination (eventually no additional messages are sent), we show that any idle-start algorithm must use ω(1) memory per node, separating the static and dynamic settings for anonymous broadcast. This lower bound is not far from optimal, as we present an algorithm that solves broadcast with stabilizing termination using 𝒪(log n) memory per node in worst-case asymptotically optimal time. In sum, these results reveal the necessity of non-constant memory for nontrivial terminating computation in anonymous dynamic networks.

Cite as

Garrett Parzych and Joshua J. Daymude. Memory Lower Bounds and Impossibility Results for Anonymous Dynamic Broadcast. In 38th International Symposium on Distributed Computing (DISC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 319, pp. 35:1-35:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{parzych_et_al:LIPIcs.DISC.2024.35,
  author =	{Parzych, Garrett and Daymude, Joshua J.},
  title =	{{Memory Lower Bounds and Impossibility Results for Anonymous Dynamic Broadcast}},
  booktitle =	{38th International Symposium on Distributed Computing (DISC 2024)},
  pages =	{35:1--35:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-352-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{319},
  editor =	{Alistarh, Dan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2024.35},
  URN =		{urn:nbn:de:0030-drops-212615},
  doi =		{10.4230/LIPIcs.DISC.2024.35},
  annote =	{Keywords: Dynamic networks, anonymity, broadcast, space complexity, lower bounds, termination detection, stabilizing termination}
}

Search Results

Documents authored by Parzych, Garrett

Brief Announcement: Adaptive Self-Organization in Anonymous Dynamic Networks

Abstract

Cite as

Memory Lower Bounds and Impossibility Results for Anonymous Dynamic Broadcast

Abstract

Cite as

Thanks for your feedback!

Could not send message