Distributed Synthesis in Continuous Time

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

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

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?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• 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
• 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
• The How and Why of Interactive Markov Chains
• Compositional Abstraction for Stochastic Systems
• Switched PIOA: parallel composition via distributed scheduling
• Asynchronous Games over Tree Architectures
• 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
• Distributed probabilistic input/output automata: expressiveness, (un)decidability and algorithms
• Compositional Verification and Optimization of Interactive Markov Chains
• Distributed Markov Chains

Cited In (3)

• Distributed synthesis for well-connected architectures
• Title not available (Why is that?)
• Distributed Synthesis in Continuous Time

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)