License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2017.26
URN: urn:nbn:de:0030-drops-83996
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8399/
Go to the corresponding LIPIcs Volume Portal

Ehlers, Rüdiger ; Finkbeiner, Bernd

Symmetric Synthesis

pdf-format:
LIPIcs-FSTTCS-2017-26.pdf (0.5 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{ehlers_et_al:LIPIcs:2018:8399,
  author =	{R{\"u}diger Ehlers and Bernd Finkbeiner},
  title =	{{Symmetric Synthesis}},
  booktitle =	{37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)},
  pages =	{26:1--26:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-055-2},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{93},
  editor =	{Satya Lokam and R. Ramanujam},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8399},
  URN =		{urn:nbn:de:0030-drops-83996},
  doi =		{10.4230/LIPIcs.FSTTCS.2017.26},
  annote =	{Keywords: Reactive Synthesis, Symmetry}
}

Keywords: Reactive Synthesis, Symmetry
Collection: 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)
Issue Date: 2018
Date of publication: 12.02.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI