Distributed synthesis in continuous time

DOI10.1007/978-3-662-49630-5_21zbMATH Open1475.68207arXiv1601.01587OpenAlexW2964105520MaRDI QIDQ2811352FDOQ2811352

Authors: Holger Hermanns, Jan Krčál, Steen Vester 

Publication date: 10 June 2016

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Abstract: We introduce a formalism modelling communication of distributed agents strictly in continuous-time. Within this framework, we study the problem of synthesising local strategies for individual agents such that a specified set of goal states is reached, or reached with at least a given probability. The flow of time is modelled explicitly based on continuous-time randomness, with two natural implications: First, the non-determinism stemming from interleaving disappears. Second, when we restrict to a subclass of non-urgent models, the quantitative value problem for two players can be solved in EXPTIME. Indeed, the explicit continuous time enables players to communicate their states by delaying synchronisation (which is unrestricted for non-urgent models). In general, the problems are undecidable already for two players in the quantitative case and three players in the qualitative case. The qualitative undecidability is shown by a reduction to decentralized POMDPs for which we provide the strongest (and rather surprising) undecidability result so far.

Full work available at URL: https://arxiv.org/abs/1601.01587

Recommendations

• Distributed Synthesis for Alternating-Time Logics
• Unlimited Decidability of Distributed Synthesis with Limited Missing Knowledge
• Natural Specifications Yield Decidability for Distributed Synthesis of Asynchronous Systems
• Fair synthesis for asynchronous distributed systems
• FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science

Mathematics Subject Classification ID

Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The Complexity of Decentralized Control of Markov Decision Processes
• Analyzing security protocols using time-bounded task-PIOAs
• Title not available (Why is that?)
• Interactive Markov chains. And the quest for quantified quality
• Calculi for synchrony and asynchrony
• Probabilistic automata on finite words: decidable and undecidable problems
• Probabilistic ω-automata
• A Theory of Communicating Sequential Processes
• Title not available (Why is that?)
• The how and why of interactive Markov chains
• Compositional abstraction for stochastic systems
• Switched PIOA: parallel composition via distributed scheduling
• Title not available (Why is that?)
• Asynchronous Games over Tree Architectures
• Title not available (Why is that?)
• Information tracking in games on graphs
• Composition and behaviors of probabilistic I/O automata
• A theory of stochastic systems. I: Stochastic automata
• Distributed synthesis in continuous time
• Title not available (Why is that?)
• Distributed probabilistic input/output automata: expressiveness, (un)decidability and algorithms
• Compositional verification and optimization of interactive Markov chains
• Distributed Markov chains

Cited In (4)

• Distributed synthesis for well-connected architectures
• Distributed synthesis in continuous time
• Title not available (Why is that?)
• Policy Synthesis for Collective Dynamics

Uses Software

• MRMC

This page was built for publication: Distributed synthesis in continuous time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2811352)