CISPA
Browse
cispa_all_3672.pdf (583.47 kB)

Translating Asynchronous Games for Distributed Synthesis

Download (583.47 kB)
conference contribution
posted on 2023-11-29, 18:12 authored by Raven BeutnerRaven Beutner, Bernd FinkbeinerBernd Finkbeiner, Jesko Hecking-Harbusch
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.

History

Preferred Citation

Raven Beutner, Bernd Finkbeiner and Jesko Hecking-Harbusch. Translating Asynchronous Games for Distributed Synthesis. In: International Conference on Concurrency Theory (CONCUR). 2019.

Primary Research Area

  • Reliable Security Guarantees

Name of Conference

International Conference on Concurrency Theory (CONCUR)

Legacy Posted Date

2022-05-06

Open Access Type

  • Green

BibTeX

@inproceedings{cispa_all_3672, title = "Translating Asynchronous Games for Distributed Synthesis", author = "Beutner, Raven and Finkbeiner, Bernd and Hecking-Harbusch, Jesko", booktitle="{International Conference on Concurrency Theory (CONCUR)}", year="2019", }

Usage metrics

    Categories

    No categories selected

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC