Sixteenth Annual IEEE Symposium on

Logic in Computer Science (LICS 2001)

Paper: Synthesizing Distributed Systems (at LICS 2001)

Authors: Orna Kupferman Moshe Y. Vardi


In system synthesis, we transform a specification into a system that is guaranteed to satisfy the specification. When the system is distributed, the goal is to construct the system's underlying processes. Results on multi-player games imply that the synthesis problem for linear specifications is undecidable for general architectures, and is nonelementary decidable for hierarchical architectures, where the processes are linearly ordered and information among them flows in one direction. In this paper we present a significant extension of this result. We handle both linear and branching specifications, and we show that a sufficient condition for decidability of the synthesis problem is a linear or cyclic order among the processes, in which information flows in either one or both directions. We also allow the processes to have internal hidden variables, and we consider communications with and without delay. Many practical applications fall into this class.


    author = 	 {Orna Kupferman and Moshe Y. Vardi},
    title = 	 {Synthesizing Distributed Systems},
    booktitle =  {Proceedings of the Sixteenth Annual IEEE Symp. on Logic in Computer Science, {LICS} 2001},
    year =	 2001,
    editor =	 {Joseph Halpern},
    month =	 {June}, 
    pages =      {389--},
    location =   {Boston, MA, USA}, 
    publisher =	 {IEEE Computer Society Press}