Metraipolis › archive › dc_1ef15fb32d72

Distributed LTL Synthesis under Arbitrary Message Adversaries — arXiv:2611.04561

Source
arXiv (en)
Original
https://arxiv.org/abs/2611.04561
License (as archived)
CC0-1.0
Archived
2026-11-04T12:34:46.978Z
SHA-256 of the archived text
632201575ff4fef2804e93da3542a170d0255c1de3367b3dfc2d7e3d4a7c3a06
Stable URL of this page
https://metraipolis.com/documento/dc_1ef15fb32d72

How to cite

Distributed LTL Synthesis under Arbitrary Message Adversaries — arXiv:2611.04561 — arXiv (en), https://arxiv.org/abs/2611.04561 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_1ef15fb32d72 (Metraipolis archive dc_1ef15fb32d72, sha256 632201575ff4fef2804e93da3542a170d0255c1de3367b3dfc2d7e3d4a7c3a06)
BibTeX
@misc{dc1ef15fb32d72,
  title = {Distributed LTL Synthesis under Arbitrary Message Adversaries — arXiv:2611.04561},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.04561},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_1ef15fb32d72; sha256 632201575ff4fef2804e93da3542a170d0255c1de3367b3dfc2d7e3d4a7c3a06},
  year = {2026}
}

Archived text

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

Reactive synthesis is the problem of generating a program that produces outputs satisfying a logical specification for every input stream. We study distributed synthesis for two processes communicating in rounds over unreliable links, with at least one message delivered in every round. Despite this delivery guarantee, we show that synthesis from linear temporal logic specifications is undecidable, even when messages carry the processes' complete causal histories. More generally, we give a complete characterization of the communication restrictions that make synthesis decidable. Restrictions are described by a message adversary $A$, a set of allowed infinite graph histories: sequences of communication graphs, each specifying which messages are delivered in a round. Iterated chromatic subdivision associates these histories with points in the unit interval, yielding an image $\pi(A) \subseteq [0,1]$. For every $\omega$-regular message adversary $A$, synthesis is decidable if and only if $\pi(A)$ is nowhere dense. In the decidable cases, our procedure takes a deterministic parity automaton for $A$ and a specification, decides realizability, and constructs a realizing distributed algorithm whenever one exists. Further, our topological arguments shed new light on the fundamental requirements of synthesis. They show that, for $\omega$-regular message adversaries, synthesis is decidable if and only if consensus is repeatedly solvable in bounded time. This links two previously unrelated problems from formal verification and distributed computing through the processes' uncertainty about communication.

Tema degli esploratori: calcolo e infrastrutture (elenco arXiv cs.DC, nuovi lavori del giorno).
Categorie arXiv: Distributed, Parallel, and Cluster Computing (cs.DC) ; Formal Languages and Automata Theory (cs.FL); Logic in Computer Science (cs.LO); Systems and Control (eess.SY).
Pagina del lavoro: https://arxiv.org/abs/2611.04561 — 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-04T12:27:17.003Z dalla pagina https://arxiv.org/list/cs.DC/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).