Document Open Access Logo

Automated Synthesis: Going Distributed (Invited Talk)

Author Anca Muscholl

PDF
Thumbnail PDF

File

LIPIcs.CSL.2016.3.pdf
  • Filesize: 213 kB
  • 2 pages

Document Identifiers

Author Details

Anca Muscholl

Cite As Get BibTex

Anca Muscholl. Automated Synthesis: Going Distributed (Invited Talk). In 25th EACSL Annual Conference on Computer Science Logic (CSL 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 62, pp. 3:1-3:2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.CSL.2016.3

Abstract

Synthesis is particularly challenging for concurrent programs. At the same time it is a very promising approach, since concurrent programs are difficult to get right, or to analyze with traditional verification techniques. The talk provides an introduction to distributed synthesis in the setting of Mazurkiewicz traces, and its applications to decentralized runtime monitoring.

Subject Classification

Keywords
  • Concurrent programs
  • Distributed synthesis
  • Runtime monitoring

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Parosh Abdulla, Stavros Aronis, Bengt Jonsson, and Konstantinos Sagonas. Optimal dynamic partial order reduction. In POPL'14, pages 373-384. ACM, 2014. Google Scholar
  2. S. Akshay, Ionut Dinca, Blaise Genest, and Alin Stefanescu. Implementing realistic asynchronous automata. In FSTTCS'13, LIPIcs, pages 213-224. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2013. Google Scholar
  3. Rajeev Alur, Ken McMillan, and Doron Peled. Model-checking of correctness conditions for concurrent objects. In LICS'96, pages 219-228. IEEE, 1996. Google Scholar
  4. Pavol Cerný, Thomas A. Henzinger, Arjun Radhakrishna, Leonid Ryzhyk, and Thorsten Tarrach. Efficient synthesis for concurrency by semantics-preserving transformations. In CAV'13, LNCS, pages 951-967. Springer, 2013. Google Scholar
  5. Alonzo Church. Logic, arithmetics, and automata. Proceedings of the International Congress of Mathematicians, 1962. Google Scholar
  6. E.M. Clarke and E.A. Emerson. Design and synthesis of synchronization skeletons using branching time temporal logic. In Workshop on Logics of Programs, volume 131 of Lecture Notes in Computer Science, pages 52-71. Springer Verlag, 1981. Google Scholar
  7. R. Cori, Y. Métivier, and W. Zielonka. Asynchronous mappings and asynchronous cellular automata. Information and Computation, 106:159-202, 1993. Google Scholar
  8. Philippe Darondeau and Laurie Ricker. Distributed control of discrete-event systems: A first step. Transactions on Petri Nets and Other Models of Concurrency, 6:24-45, 2012. Google Scholar
  9. Volker Diekert and Grzegorz Rozenberg, editors. The Book of Traces. World Scientific, Singapore, 1995. Google Scholar
  10. Azadeh Farzan and Parthasarathy Madhusudan. Monitoring atomicity in concurrent programs. In CAV'08, LNCS, pages 52-65. Springer, 2008. Google Scholar
  11. Bernd Finkbeiner and Ernst-Ruediger Olderog. Petri games: Synthesis of distributed systems with causal memory. In GandALF'14, EPTCS, pages 217-230, 2014. Google Scholar
  12. Bernd Finkbeiner and Sven Schewe. Uniform distributed synthesis. In LICS'05, pages 321-330. IEEE, 2005. Google Scholar
  13. Paul Gastin, Benjamin Lerman, and Marc Zeitoun. Distributed games with causal memory are decidable for series-parallel systems. In FSTTCS'04, LNCS, pages 275-286. Springer, 2004. Google Scholar
  14. Paul Gastin and Nathalie Sznajder. Fair synthesis for asynchronous distributed systems. ACM Transactions on Computational Logic, 14(2):9, 2013. Google Scholar
  15. Blaise Genest, Hugo Gimbert, Anca Muscholl, and Igor Walukiewicz. Optimal Zielonka-type construction of deterministic asynchronous automata. In ICALP'10, LNCS, pages 52-63. Springer, 2010. Google Scholar
  16. R.M. Karp and R. E. Miller. Parallel program schemata. Journal of Computer and System Sciences, 3:147-195, 1969. Google Scholar
  17. Siddharth Krishna and Anca Muscholl. A quadratic construction for Zielonka automata with acyclic communication structure. Theoretical Computer Science, 503:109-114, 2013. Google Scholar
  18. Orna Kupferman and Moshe Y. Vardi. Synthesizing distributed systems. In LICS'01, pages 389-398. IEEE, 2001. Google Scholar
  19. Leslie Lamport. Time, clocks, and the ordering of events in a distributed system. Operating Systems, 21(7):558-565, 1978. Google Scholar
  20. P. Madhusudan, P. S. Thiagarajan, and S. Yang. The MSO theory of connectedly communicating processes. In FSTTCS'05, LNCS, pages 201-212. Springer, 2005. Google Scholar
  21. P. Madhusudan and P.S. Thiagarajan. Distributed control and synthesis for local specifications. In ICALP'01, volume 2076 of LNCS, pages 396-407. Springer, 2001. Google Scholar
  22. Antoni Mazurkiewicz. Concurrent program schemes and their interpretations. DAIMI Rep. PB 78, Aarhus University, Aarhus, 1977. Google Scholar
  23. Madhavan Mukund and Milind A. Sohoni. Keeping track of the latest gossip in a distributed system. Distributed Computing, 10(3):137-148, 1997. Google Scholar
  24. Anca Muscholl and Igor Walukiewicz. Distributed synthesis for acyclic architectures. In FSTTCS'14, LIPIcs, pages 639-651. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2014. Google Scholar
  25. Doron A. Peled. All from one, one for all: on model checking using representatives. In CAV'93, LNCS, pages 409-423. Springer, 1993. Google Scholar
  26. G. L. Peterson and J. H. Reif. Multi-person alternation. In FOCS'79, pages 348-363. IEEE, 1979. Google Scholar
  27. A. Pnueli and R. Rosner. On the synthesis of a reactive module. In Proc. ACM POPL, pages 179-190, 1989. Google Scholar
  28. Amir Pnueli and Roni Rosner. Distributed reactive systems are hard to synthesize. In FOCS'90. IEEE, 1990. Google Scholar
  29. M. O. Rabin. Automata on Infinite Objects and Church’s Problem. American Mathematical Society, Providence, RI, 1972. Google Scholar
  30. P.J.G. Ramadge and W.M. Wonham. The control of discrete event systems. Proceedings of the IEEE, 77(2):81-98, 1989. Google Scholar
  31. Koushik Sen, Abhay Vardhan, Gul Agha, and Grigore Rosu. Decentralized runtime analysis of multithreaded applications. In International Parallel and Distributed Processing Symposium (IPDPS 2006). IEEE, 2006. Google Scholar
  32. Alin Stefanescu. Automatic synthesis of distributed transition systems. PhD thesis, Universität Stuttgart, 2006. Google Scholar
  33. W. Zielonka. Notes on finite asynchronous automata. RAIRO-Theoretical Informatics and Applications, 21:99-135, 1987. Google Scholar
  34. W. Zielonka. Asynchronous automata. In G. Rozenberg and V. Diekert, editors, Book of Traces, pages 175-217. World Scientific, Singapore, 1995. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact