2026-07-20T05:24:25Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8399 2024-03-06T10:41:58Z ddc:004 open_access

Symmetric Synthesis Ehlers, Rüdiger Finkbeiner, Bernd Reactive Synthesis Symmetry We study the problem of determining whether a given temporal specification can be implemented by a symmetric system, i.e., a system composed from identical components. Symmetry is an important goal in the design of distributed systems, because systems that are composed from identical components are easier to build and maintain. We show that for the class of rotation-symmetric architectures, i.e., multi-process architectures where all processes have access to all system inputs, but see different rotations of the inputs, the symmetric synthesis problem is EXPTIME-complete in the number of processes. In architectures where the processes do not have access to all input variables, the symmetric synthesis problem becomes undecidable, even in cases where the standard distributed synthesis problem is decidable. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Rüdiger Ehlers and Bernd Finkbeiner 2018 Is Part Of LIPIcs, Volume 93, 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2017.26 urn:nbn:de:0030-drops-83996 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2017.26 eng https://creativecommons.org/licenses/by/3.0/legalcode