2026-07-29T12:26:41Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25093 2025-12-09T15:09:11Z ddc:004 open_access

Synthesising Full-Information Protocols Berwanger, Dietmar Doyen, Laurent Soullard, Thomas Infinite Games on Finite Graphs Imperfect Information Reactive Processes Distributed Synthesis Dynamic Networks We study a communication model where processes reveal their entire local information whenever they interact. However, the system involves an indeterminate environment that may control when a communication event occurs and which participants are involved. As a result, the amount of information a process may receive at once is unbounded. Such full-information protocols are common in the distributed-computing literature. Here, we consider synchronous systems, modelled as infinite games with imperfect information played on finite graphs. We present a decision procedure for the synthesis of a process with an ω-regular specification in a system where the other participating processes are fixed. The challenge lies in constructing a finite representation of information trees with unbounded branching. Our construction is non-elementary in the size of the problem instance, and we establish a matching non-elementary lower bound for the complexity of the synthesis problem. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Dietmar Berwanger and Laurent Doyen and Thomas Soullard 2025 Is Part Of LIPIcs, Volume 360, 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2025.13 urn:nbn:de:0030-drops-250930 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2025.13 eng https://creativecommons.org/licenses/by/4.0/legalcode