{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:10:41Z","timestamp":1760202641029,"version":"3.41.0"},"reference-count":43,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2013,6,1]],"date-time":"2013-06-01T00:00:00Z","timestamp":1370044800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100003990","name":"Conseil R\u00e9gional, \u00cele-de-France","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100003990","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004963","name":"Seventh Framework Programme","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100004963","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Logic"],"published-print":{"date-parts":[[2013,6]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.1145\/2480759.2480761","type":"journal-article","created":{"date-parts":[[2013,6,18]],"date-time":"2013-06-18T12:36:08Z","timestamp":1371558968000},"page":"1-31","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Fair Synthesis for Asynchronous Distributed Systems"],"prefix":"10.1145","volume":"14","author":[{"given":"Paul","family":"Gastin","sequence":"first","affiliation":[{"name":"LSV, ENS Cachan, INRIA, CNRS"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nathalie","family":"Sznajder","sequence":"additional","affiliation":[{"name":"LIP6\/MoVe, Universit\u00e9 Pierre &amp; Marie Curie, CNRS"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2013,6]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","unstructured":"Anuchitankul A.\n     and \n      Manna Z\n  . \n  1994\n  . Realizability and synthesis of reactive modules. In Proceedings of the 6th International Conference on Computer Aided Verification (CAV\u201994). D. L. Dill Ed. Lecture Notes in Computer Science vol. \n  818 Springer 156--168.   Anuchitankul A. and Manna Z. 1994. Realizability and synthesis of reactive modules. In Proceedings of the 6th International Conference on Computer Aided Verification (CAV\u201994) . D. L. Dill Ed. Lecture Notes in Computer Science vol. 818 Springer 156--168.","DOI":"10.1007\/3-540-58179-0_51"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(02)00442-5"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-04081-8_9"},{"volume-title":"Proceedings of the 16th IEEE Annual Symposium on Logic in Computer Science (LICS\u201901)","author":"Bouajjani A.","key":"e_1_2_1_4_1","unstructured":"Bouajjani , A. , Muscholl , A. , and Touili , T . 2001. Permutation rewriting and algorithmic verification . In Proceedings of the 16th IEEE Annual Symposium on Logic in Computer Science (LICS\u201901) . IEEE Press. Bouajjani, A., Muscholl, A., and Touili, T. 2001. Permutation rewriting and algorithmic verification. In Proceedings of the 16th IEEE Annual Symposium on Logic in Computer Science (LICS\u201901). IEEE Press."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1969-0280205-0"},{"key":"e_1_2_1_6_1","volume-title":"-E","author":"Cano A.","year":"2011","unstructured":"Cano , A. , Guaiana , G. , and Pin , J . -E . 2011 . Closure of regular languages under semi-commutations. http:\/\/liafa.jussieu.fr\/jep\/PDF\/PartialCommutationsRed.pdf. Cano, A., Guaiana, G., and Pin, J.-E. 2011. Closure of regular languages under semi-commutations. http:\/\/liafa.jussieu.fr\/jep\/PDF\/PartialCommutationsRed.pdf."},{"key":"e_1_2_1_7_1","volume-title":"-E","author":"Carton O.","year":"2008","unstructured":"Carton , O. , Perrin , D. , and Pin , J . -E . 2008 . Automata and semigroups recognizing infinite words. In Logic and Automata: History and Perspectives {in Honor of Wolfgang Thomas}. J. Flum, E. Gr\u00e4del, and T. Wilke Eds., Texts in Logic and Games Series, vol. 2 , Amsterdam University Press , 133--168. Carton, O., Perrin, D., and Pin, J.-E. 2008. Automata and semigroups recognizing infinite words. In Logic and Automata: History and Perspectives {in Honor of Wolfgang Thomas}. J. Flum, E. Gr\u00e4del, and T. Wilke Eds., Texts in Logic and Games Series, vol. 2, Amsterdam University Press, 133--168."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1051\/ita:2007029"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-95891-8_16"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the International Congress of Mathematicians. 23--35","author":"Church A.","year":"1963","unstructured":"Church , A. 1963 . Logic, arithmetics, and automata . In Proceedings of the International Congress of Mathematicians. 23--35 . Church, A. 1963. Logic, arithmetics, and automata. In Proceedings of the International Congress of Mathematicians. 23--35."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(87)90040-X"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)90280-1"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1995.1010"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/1987389.1987421"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6423(83)90017-5"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02658-4_22"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2005.53"},{"key":"e_1_2_1_18_1","unstructured":"Finkbeiner B.\n     and \n      Schewe S\n  . \n  2006\n  . Synthesis of asynchronous systems. In Proceedings of the International Symposium on Logic-Based Program Synthesis and Transformation (LOPSTR\u201906). G. Puebla Ed. Lecture Notes in Computer Science vol. \n  4407 Springer 127--142.   Finkbeiner B. and Schewe S. 2006. Synthesis of asynchronous systems. In Proceedings of the International Symposium on Logic-Based Program Synthesis and Transformation (LOPSTR\u201906) . G. Puebla Ed. Lecture Notes in Computer Science vol. 4407 Springer 127--142."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30538-5_23"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10703-008-0064-7"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(89)90098-4"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/FMCAD.2006.22"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.2307\/421091"},{"key":"e_1_2_1_24_1","doi-asserted-by":"crossref","unstructured":"Kupferman O.\n     and \n      Vardi M. Y\n  . \n  2000\n  . &mu;-calculus synthesis. In Proceedings of the 25th International Symposium on Mathematical Foundations of Computer Science (MFCS\u201900). M. Nielsen and B. Rovan Eds. Lecture Notes in Computer Science Series vol. \n  1893 Springer 497--507.   Kupferman O. and Vardi M. Y. 2000. &mu; -calculus synthesis. In Proceedings of the 25th International Symposium on Mathematical Foundations of Computer Science (MFCS\u201900) . M. Nielsen and B. Rovan Eds. Lecture Notes in Computer Science Series vol. 1893 Springer 497--507.","DOI":"10.1007\/3-540-44612-5_45"},{"volume-title":"Proceedings of the 16th IEEE Annual Symposium on Logic in Computer Science (LICS\u201901)","author":"Kupferman O.","key":"e_1_2_1_25_1","unstructured":"Kupferman , O. and Vardi , M. Y . 2001. Synthesizing distributed systems . In Proceedings of the 16th IEEE Annual Symposium on Logic in Computer Science (LICS\u201901) . J. Y. Halpern Ed., IEEE. Kupferman, O. and Vardi, M. Y. 2001. Synthesizing distributed systems. In Proceedings of the 16th IEEE Annual Symposium on Logic in Computer Science (LICS\u201901). J. Y. Halpern Ed., IEEE."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.66"},{"key":"e_1_2_1_27_1","first-page":"219","article-title":"An introduction to input\/output automata","volume":"2","author":"Lynch N.","year":"1989","unstructured":"Lynch , N. and Tuttle , M. R. 1989 . An introduction to input\/output automata . CWI-Quart. 2 , 3, 219 -- 246 . Lynch, N. and Tuttle, M. R. 1989. An introduction to input\/output automata. CWI-Quart. 2, 3, 219--246.","journal-title":"CWI-Quart."},{"key":"e_1_2_1_28_1","doi-asserted-by":"crossref","unstructured":"Madhusudan P.\n     and \n      Thiagarajan P. S\n  . \n  2001\n  . Distributed control and synthesis for local specifications. In Proceedings of the 28th International Colloquium on Automata Languages and Programming (ICALP\u201901). F. Orejas P. G. Spirakis and J. van Leeuwen Eds. Lecture Notes in Computer Science vol. \n  2076 Springer 396--407.   Madhusudan P. and Thiagarajan P. S. 2001. Distributed control and synthesis for local specifications. In Proceedings of the 28th International Colloquium on Automata Languages and Programming (ICALP\u201901) . F. Orejas P. G. Spirakis and J. van Leeuwen Eds. Lecture Notes in Computer Science vol. 2076 Springer 396--407.","DOI":"10.1007\/3-540-48224-5_33"},{"key":"e_1_2_1_29_1","doi-asserted-by":"crossref","unstructured":"Madhusudan P.\n     and \n      Thiagarajan P. S\n  . \n  2002\n  . A decidable class of asynchronous distributed controllers. In Proceedings of the 13th International Conference on Concurrency Theory (CONCUR\u201902). L. Brim P. Jan\u010dar M. Kret\u00ednsk\u00fd and A. Kucera Eds. Lecture Notes in Computer Science vol. \n  2421 Springer 145--160.   Madhusudan P. and Thiagarajan P. S. 2002. A decidable class of asynchronous distributed controllers. In Proceedings of the 13th International Conference on Concurrency Theory (CONCUR\u201902) . L. Brim P. Jan\u010dar M. Kret\u00ednsk\u00fd and A. Kucera Eds. Lecture Notes in Computer Science vol. 2421 Springer 145--160.","DOI":"10.1007\/3-540-45694-5_11"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/11590156_16"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/357233.357237"},{"volume-title":"Concurrent program schemes and their interpretations. DAIMI report PB 78","author":"Mazurkiewicz A.","key":"e_1_2_1_32_1","unstructured":"Mazurkiewicz , A. 1977. Concurrent program schemes and their interpretations. DAIMI report PB 78 , Aarhus University . Mazurkiewicz, A. 1977. Concurrent program schemes and their interpretations. DAIMI report PB 78, Aarhus University."},{"key":"e_1_2_1_33_1","doi-asserted-by":"crossref","unstructured":"Mohalik S.\n     and \n      Walukiewicz I\n  . \n  2003\n  . Distributed games. In Proceedings of the 23rd Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS\u201903). P. K. Pandya and J. Radhakrishnan Eds. Lecture Notes in Computer Science vol. \n  2914 Springer 338--351.  Mohalik S. and Walukiewicz I. 2003. Distributed games. In Proceedings of the 23rd Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS\u201903) . P. K. Pandya and J. Radhakrishnan Eds. Lecture Notes in Computer Science vol. 2914 Springer 338--351.","DOI":"10.1007\/978-3-540-24597-1_29"},{"key":"e_1_2_1_34_1","series-title":"Teubner-Texte zur Informatik Series","volume-title":"\u00dcber die Erkennbarkeit unendlicher Spuren","author":"Muscholl A.","unstructured":"Muscholl , A. 1996. \u00dcber die Erkennbarkeit unendlicher Spuren . Teubner-Texte zur Informatik Series , vol. 17 , Teubner . Muscholl, A. 1996. \u00dcber die Erkennbarkeit unendlicher Spuren. Teubner-Texte zur Informatik Series, vol. 17, Teubner."},{"volume-title":"Perspectives in Concurrency Theory","author":"Muscholl A.","key":"e_1_2_1_35_1","unstructured":"Muscholl , A. , Walukiewicz , I. , and Zeitoun , M. 2009. A look at the control of asynchronous automata . In Perspectives in Concurrency Theory , K. Lodaya, M. Mukund, and R. R. Eds., Universities Press , 356--371. Muscholl, A., Walukiewicz, I., and Zeitoun,M. 2009. A look at the control of asynchronous automata. In Perspectives in Concurrency Theory, K. Lodaya, M. Mukund, and R. R. Eds., Universities Press, 356--371."},{"key":"e_1_2_1_36_1","first-page":"191","article-title":"Semi-commutation for P-T Systems","volume":"38","author":"Ochmanski E.","year":"1989","unstructured":"Ochmanski , E. 1989 . Semi-commutation for P-T Systems . Bull Eur. Assoc. Theoretical Comput. Sci. 38 , 191 -- 198 . Ochmanski, E. 1989. Semi-commutation for P-T Systems. Bull Eur. Assoc. Theoretical Comput. Sci. 38, 191--198.","journal-title":"Bull Eur. Assoc. Theoretical Comput. Sci."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00219-3"},{"key":"e_1_2_1_38_1","volume-title":"-E","author":"Perrin D.","year":"2004","unstructured":"Perrin , D. and Pin , J . -E . 2004 . Infinite Words. Pure and Applied Mathematics Series, vol. 141 , Elsevier . Perrin, D. and Pin, J.-E. 2004. Infinite Words. Pure and Applied Mathematics Series, vol. 141, Elsevier."},{"key":"e_1_2_1_39_1","doi-asserted-by":"crossref","unstructured":"Pnueli A.\n     and \n      Rosner R\n  . \n  1989\n  . On the synthesis of an asynchronous reactive module. In Proceedings of the 16th International Colloquium on Automata Languages and Programming (ICALP\u201989). G. Ausiello M. Dezani-Ciancaglini and S. R. D. Rocca Eds. Lecture Notes in Computer Science Series vol. \n  372 Springer 652--671.   Pnueli A. and Rosner R. 1989. On the synthesis of an asynchronous reactive module. In Proceedings of the 16th International Colloquium on Automata Languages and Programming (ICALP\u201989) . G. Ausiello M. Dezani-Ciancaglini and S. R. D. Rocca Eds. Lecture Notes in Computer Science Series vol. 372 Springer 652--671.","DOI":"10.1007\/BFb0035790"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/FSCS.1990.89597"},{"volume-title":"Automata on Infinite Objects and Church\u2019s Problem","author":"Rabin M. O.","key":"e_1_2_1_41_1","unstructured":"Rabin , M. O. 1972. Automata on Infinite Objects and Church\u2019s Problem . American Mathematical Society . Rabin, M. O. 1972. Automata on Infinite Objects and Church\u2019s Problem. American Mathematical Society."},{"key":"e_1_2_1_42_1","doi-asserted-by":"crossref","unstructured":"Stef\u00e3nescu A. Esparza J. and \n      Muscholl A\n  . \n  2003\n  . Synthesis of distributed algorithms using asynchronous automata. In Proceedings of the 14th International Conference on Concurrency Theory (CONCUR\u201903). R. Amadio and D. Lugiez Eds. Lecture Notes in Computer Science Series vol. \n  2761 Springer 27--41.  Stef\u00e3nescu A. Esparza J. and Muscholl A. 2003. Synthesis of distributed algorithms using asynchronous automata. In Proceedings of the 14th International Conference on Concurrency Theory (CONCUR\u201903) . R. Amadio and D. Lugiez Eds. Lecture Notes in Computer Science Series vol. 2761 Springer 27--41.","DOI":"10.1007\/978-3-540-45187-7_2"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.5555\/647764.735830"}],"container-title":["ACM Transactions on Computational Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2480759.2480761","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2480759.2480761","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:39:14Z","timestamp":1750235954000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2480759.2480761"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,6]]},"references-count":43,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2013,6]]}},"alternative-id":["10.1145\/2480759.2480761"],"URL":"https:\/\/doi.org\/10.1145\/2480759.2480761","relation":{},"ISSN":["1529-3785","1557-945X"],"issn-type":[{"type":"print","value":"1529-3785"},{"type":"electronic","value":"1557-945X"}],"subject":[],"published":{"date-parts":[[2013,6]]},"assertion":[{"value":"2010-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-06-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}