Paper Info
Title
Natural Specifications Yield Decidability for Distributed Synthesis of Asynchronous Systems
Abstract
We study the synthesis problem in an asynchronous distributed setting: a finite set of processes interact locally with an uncontrollable environment and communicate with each other by sending signals --- actions that are immediately received by the target process. The synthesis problem is to come up with a local strategy for each process such that the resulting behaviours of the system meet a given specification. We consider external specifications over partial orders . External means that specifications only relate input and output actions from and to the environment and not signals exchanged by processes. We also ask for some closure properties of the specification. We present this new setting for studying the distributed synthesis problem, and give decidability results: the non-distributed case, and the subclass of networks where communication happens through a strongly connected graph. We believe that this framework for distributed synthesis yields decidability results for many more architectures.
Year
DOI
Venue
2009
10.1007/978-3-540-95891-8_16
SOFSEM
Keywords
Field
DocType
natural specifications yield decidability,closure property,synthesis yields decidability result,uncontrollable environment,new setting,external specification,external mean,decidability result,asynchronous systems,finite set,synthesis problem,target process,connected graph,partial order,asynchronous system
Discrete mathematics,Asynchronous communication,Combinatorics,Ask price,Finite set,Computer science,Decidability,Theoretical computer science,Input/output,Connectivity
Conference
Volume
ISSN
Citations 
5404
0302-9743
5
PageRank 
References 
Authors
0.44
17
3
Name
Order
Citations
PageRank
Thomas Chatain1161.46
Paul Gastin2116575.66
Nathalie Sznajder3365.18