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.CONCUR.2019.26
URN: urn:nbn:de:0030-drops-109289
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10928/
Go to the corresponding LIPIcs Volume Portal

Beutner, Raven ; Finkbeiner, Bernd ; Hecking-Harbusch, Jesko

Translating Asynchronous Games for Distributed Synthesis

pdf-format:
LIPIcs-CONCUR-2019-26.pdf (0.6 MB)

Abstract

In distributed synthesis, a set of process implementations is generated, which together, accomplish an objective against all possible behaviors of the environment. A lot of recent work has focussed on systems with causal memory, i.e., sets of asynchronous processes that exchange their causal histories upon synchronization. Decidability results for this problem have been stated either in terms of control games, which extend Zielonka's asynchronous automata by partitioning the actions into controllable and uncontrollable, or in terms of Petri games, which extend Petri nets by partitioning the tokens into system and environment players. The precise connection between these two models was so far, however, an open question.
In this paper, we provide the first formal connection between control games and Petri games. We establish the equivalence of the two game types based on weak bisimulations between their strategies. For both directions, we show that a game of one type can be translated into an equivalent game of the other type. We provide exponential upper and lower bounds for the translations. Our translations allow to transfer and combine decidability results between the two types of games. Exemplarily, we translate decidability in acyclic communication architectures, originally obtained for control games, to Petri games, and decidability in single-process systems, originally obtained for Petri games, to control games.

BibTeX - Entry

@InProceedings{beutner_et_al:LIPIcs:2019:10928,
  author =	{Raven Beutner and Bernd Finkbeiner and Jesko Hecking-Harbusch},
  title =	{{Translating Asynchronous Games for Distributed Synthesis}},
  booktitle =	{30th International Conference on Concurrency Theory (CONCUR 2019)},
  pages =	{26:1--26:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-121-4},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{140},
  editor =	{Wan Fokkink and Rob van Glabbeek},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/10928},
  URN =		{urn:nbn:de:0030-drops-109289},
  doi =		{10.4230/LIPIcs.CONCUR.2019.26},
  annote =	{Keywords: synthesis, distributed systems, causal memory, Petri games, control games}
}

Keywords: synthesis, distributed systems, causal memory, Petri games, control games
Collection: 30th International Conference on Concurrency Theory (CONCUR 2019)
Issue Date: 2019
Date of publication: 20.08.2019

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