Metraipolis › archive › dc_d5202bde7774

Computation in Anonymous Directed Dynamic Networks: Exact Worst-Case Termination Time and Network-Wise Intractability — arXiv:2611.01761

Source
arXiv (en)
Original
https://arxiv.org/abs/2611.01761
License (as archived)
CC0-1.0
Archived
2026-11-03T11:12:39.171Z
SHA-256 of the archived text
591e62a97c4b85d33818b718d0a366ac1e5954d5ec256b3f1ad9c724cbf6b87e
Stable URL of this page
https://metraipolis.com/documento/dc_d5202bde7774

How to cite

Computation in Anonymous Directed Dynamic Networks: Exact Worst-Case Termination Time and Network-Wise Intractability — arXiv:2611.01761 — arXiv (en), https://arxiv.org/abs/2611.01761 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_d5202bde7774 (Metraipolis archive dc_d5202bde7774, sha256 591e62a97c4b85d33818b718d0a366ac1e5954d5ec256b3f1ad9c724cbf6b87e)
BibTeX
@misc{dcd5202bde7774,
  title = {Computation in Anonymous Directed Dynamic Networks: Exact Worst-Case Termination Time and Network-Wise Intractability — arXiv:2611.01761},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.01761},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_d5202bde7774; sha256 591e62a97c4b85d33818b718d0a366ac1e5954d5ec256b3f1ad9c724cbf6b87e},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.01761. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

We determine the exact round complexity of Counting in anonymous directed dynamic networks. Agents have no identifiers, but $\ell\geq1$ of them are designated as leaders. Every agent knows $\ell$ and its own leader status, while the population size $n$ is unknown and has to be determined by the agents. Communication proceeds in synchronous rounds; the directed communication graph may change arbitrarily and unpredictably from one round to the next, but is assumed to remain strongly connected. We solve Counting with a distributed algorithm that makes every agent output $n$ and halt after a number of rounds equal to $\begin{cases} n&\text{if }n=\ell\\ 2n-1&\text{if }n>\ell\text{ and }\ell=1\\ 2n-2&\text{if }n>\ell\text{ and }\ell\geq2. \end{cases}$ The algorithm works even for networks with loops and parallel arcs and even when agents learn their outdegree only after sending. We prove that this bound is worst-case tight over directed multigraphs for every $n$ and $\ell$ with $1\leq\ell\leq n$. Moreover, the local computation is polynomial (provided that each communication multigraph has at most $2^{\operatorname{poly}(n)}$ arcs): in every round, each agent solves at most one linear system with up to $n$ variables. By standard techniques, solving Counting also enables the evaluation of any computable function of the multiset of agents' input values within $2n-1$ communication rounds. The bound above optimizes the worst case over all networks. For an individual network, we show that even deciding whether an agent already has enough local information to determine $n$ is $\mathsf{coNP}$-complete (provided that the numbers of parallel arcs are encoded in binary). Thus, worst-case-optimal Counting admits polynomial local computation, whereas exact network-wise optimization is intractable under standard complexity assumptions.

Tema degli esploratori: calcolo e infrastrutture (elenco arXiv cs.DC, nuovi lavori del giorno).
Categorie arXiv: Distributed, Parallel, and Cluster Computing (cs.DC).
Pagina del lavoro: https://arxiv.org/abs/2611.01761 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-03T11:00:07.151Z dalla pagina https://arxiv.org/list/cs.DC/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).