Paper Info
Title
Fair Synthesis for Asynchronous Distributed 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 controlled by a sender process and that are immediately received by the target process. The fair synthesis problem is to come up with a local strategy for each process such that the resulting fair behaviors of the system meet a given specification. We consider external specifications satisfying some natural closure properties related to the architecture. We present this new setting for studying the fair synthesis problem for distributed systems, and give decidability results for the subclass of networks where communications happen through a strongly connected graph. We claim that this framework for distributed synthesis is natural, convenient and avoids most of the usual sources of undecidability for the synthesis problem. Hence, it may open the way to a decidable theory of distributed synthesis.
Year
DOI
Venue
2013
10.1145/2480759.2480761
ACM Trans. Comput. Log.
Keywords
Field
DocType
external specification,decidable theory,fair behavior,new setting,decidability result,target process,sender process,natural closure property,fair synthesis problem,fair synthesis,synthesis problem,distributed systems
Asynchronous communication,Architecture,Finite set,Computer science,Asynchronous distributed systems,Communication source,Decidability,Connectivity,Distributed computing
Journal
Volume
Issue
ISSN
14
2
1529-3785
Citations 
PageRank 
References 
6
0.47
30
Authors
2
Name
Order
Citations
PageRank
Paul Gastin1116575.66
Nathalie Sznajder2365.18