Distributed synthesis for acyclic architectures

DOI10.4230/LIPICS.FSTTCS.2014.639MaRDI QIDQ2978553zbMATH OpenOpenAlexFDO

Authors Anca Muscholl, Igor Walukiewicz

Publication date 25 April 2017

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

zbMATH Keywords

causal memorydistributed controldistributed synthesis

Mathematics Subject Classification ID

Distributed systems (68M14) Formal languages and automata (68Q45) Specification and verification (program logics, model checking, etc.) (68Q60) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Abstract: The distributed synthesis problem is about constructing cor- rect distributed systems, i.e., systems that satisfy a given specification. We consider a slightly more general problem of distributed control, where the goal is to restrict the behavior of a given distributed system in order to satisfy the specification. Our systems are finite state machines that communicate via rendez-vous (Zielonka automata). We show decidability of the synthesis problem for all omega-regular local specifications, under the restriction that the communication graph of the system is acyclic. This result extends a previous decidability result for a restricted form of local reachability specifications.

Recommendations

• Distributed synthesis for regular and contextfree specifications
• scientific article; zbMATH DE number 1754607
• Distributed synthesis for regular and contextfree specifications
• On Distributed Program Specification and Synthesis in Architectures with Cycles
• Natural Specifications Yield Decidability for Distributed Synthesis of Asynchronous Systems

Cited in

(32)

• Hierarchical information and the synthesis of distributed strategies
• Decidability of well-connectedness for distributed synthesis
• Synthesis in presence of dynamic links
• Canonical representations for direct generation of strategies in high-level Petri games
• Solving high-level Petri games
• Distributed synthesis for regular and contextfree specifications
• Distributed synthesis is simply undecidable
• Fair synthesis for asynchronous distributed systems
• Distributed synthesis for regular and contextfree specifications
• On Distributed Monitoring and Synthesis
• Efficient trace encodings of bounded synthesis for asynchronous distributed systems
• Automated synthesis of distributed controllers
• Distributed Synthesis for Alternating-Time Logics
• Natural Specifications Yield Decidability for Distributed Synthesis of Asynchronous Systems
• On Distributed Program Specification and Synthesis in Architectures with Cycles
• scientific article; zbMATH DE number 1500652 (Why is no real title available?)
• Synthesis: words and traces
• Practical distributed control synthesis
• Distributed Asynchronous Games With Causal Memory are Undecidable
• Automated synthesis: a distributed viewpoint
• Symmetric synthesis
• scientific article; zbMATH DE number 7278100 (Why is no real title available?)
• On the control of asynchronous automata
• Petri games: synthesis of distributed systems with causal memory
• Infinite games with finite knowledge gaps
• Distributed Synthesis for Well-Connected Architectures
• Translating asynchronous games for distributed synthesis
• High-level representation of benchmark families for Petri games
• Synthesis of distributed agreement-based systems with efficiently-decidable verification
• Asynchronous transition system games for two processes and their analysis
• Distributed controller synthesis for deadlock avoidance
• Distributed synthesis for well-connected architectures

This page was built for publication: Distributed synthesis for acyclic architectures

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