Compositionality Seminar, Winter 2007/2008

Prof. Kirsch, Department of Computer Sciences, University of Salzburg


Time, Location: Th 10-12 in T04, Techno-Z. First lecture on Th, October 11, 2007. Check schedule for updates.

Brief Overview: Compositional modeling and programming is key to designing and implementing integrated software systems for many applications such as multimedia and telecommunications. However, while compositional methodologies in other engineering disciplines such as electrical and mechanical engineering have already been established decades ago, software systems engineering is often non-compositional and therefore expensive and suffers from limited scalability. For example, even creating a single software process on a typical operating system such as Linux may have profound and unpredictable effects on all other processes already running on the system because the process model of most modern operating systems is to a large extent non-compositional. How can we then create systems with many, possibly thousands of processes and still provide any guarantees on correct functional and temporal behavior? If you are interested in these and other systems-related questions, sign up for the compositionality seminar. The seminar provides a unique opportunity to meet other students and discuss hot topics in systems research. Pick a research paper (or problem) provided in class (or propose some other recent paper), read and understand it, and then share your experience with the group.

Goals of the seminar: Learn how to read, understand, and present top research papers on compositionality in concurrent systems design and engineering.

Prerequisites: Background in data structures and algorithms as well as programming language and operating system concepts.

Requirements: Each student selects a research paper (or problem), gives a 45min presentation on the paper, and uploads the presentation to the seminar wiki. Seminar language is English.

Students:

Silviu Craciunas (scraciunas at cs uni-salzburg at): Compositional Real-Time Scheduling, by Insik Shin, Insup Lee. RTSS 2004. Presentation

Patricia Derler (patricia derler at cs uni-salzburg at): A Programming Model for Time-Synchronized Distributed Real-Time Systems, by Yang Zhao, Jie Liu, Edward A. Lee. RTAS 07. Presentation

Hannes Payer (hpayer at cs uni-salzburg at): A Hierarchical Coordination Language for Interacting Real-Time Tasks, by Arkadeb Ghosal, Christoph M. Kirsch, Thomas A. Henzinger, Daniel Iercan, Alberto Sangiovanni-Vincentelli. EMSOFT 2006. Presentation.

Johannes Pletzer (johannes.pletzer at cs uni-salzburg at): Incremental Schedulability Analysis of Hierarchical Real-Time Components, by Arvind Easwaran, Insik Shin, Oleg Sokolsky, Insup Lee. EMSOFT 2006. Presentation.

Harald Roeck (hroeck at cs uni-salzburg at): Periodic Resource Model for Compositional Real-Time Guarantees, by Insik Shin and Insup Lee. RTSS 2003. Presentation.

Robert Staudinger (rstaudinger at cs uni-salzburg at): Real-time Calculus for Scheduling Hard Real-Time Systems, by Lothar Thiele, Samarjit Chakraborty, Martin Naedele. International Symposium on Circuits and Systems ISCAS 2000. Presentation.

Rainer Trummer (rtrummer at cs uni-salzburg at): Composable Code Generation for Distributed Giotto, by Thomas A. Henzinger, Christoph M. Kirsch, Slobodan Matic. LCTES 2005. Presentation.

Tobias Berka (tberka at cosy sbg ac at): Bisimulation can't be traced, by Bard Bloom, Sorin Istrail, Albert R. Meyer. JACM Vol.42(1), 1995. Presentation.

Paul Rehrl (prehrl at cosy sbg ac at): Interface Theories for Component-Based Design, by Luca de Alfaro, Thomas A. Henzinger. EMSOFT 2001. Presentation

Elias Pschernig (epschern at cosy sbg ac at): Compositionality for Markov reward chains with fast transitions, by Jasen Markovski, Ana Sokolova, Nikola Trcka, Erik de Vink. EPEW 2007. Presentation


Potential Papers:

  1. A Hierarchical Coordination Language for Interacting Real-Time Tasks, by Arkadeb Ghosal, Christoph M. Kirsch, Thomas A. Henzinger, Daniel Iercan, Alberto Sangiovanni-Vincentelli. EMSOFT 2006.

  2. Composable Code Generation for Distributed Giotto, by Thomas A. Henzinger, Christoph M. Kirsch, Slobodan Matic. LCTES 2005.

  3. Periodic Resource Model for Compositional Real-Time Guarantees, by Insik Shin and Insup Lee. RTSS 2003.

  4. Compositional Real-Time Scheduling, by Insik Shin, Insup Lee. RTSS 2004.

  5. An Interface Algebra for Real-time Components, by Thomas A. Henzinger, Slobodan Matic. RTAS 2006.

  6. Incremental Schedulability Analysis of Hierarchical Real-Time Components, by Arvind Easwaran, Insik Shin, Oleg Sokolsky, Insup Lee. EMSOFT 2006.

  7. Real-time Calculus for Scheduling Hard Real-Time Systems, by Lothar Thiele, Samarjit Chakraborty, Martin Naedele. International Symposium on Circuits and Systems ISCAS 2000.

  8. Real-Time Interfaces for Composing Real-Time Systems, by Lothar Thiele, Ernesto Wandeler, Nikolay Stoimenov. EMSOFT 2006.

  9. Interface Theories for Component-Based Design, by Luca de Alfaro, Thomas A. Henzinger. EMSOFT 2001.

  10. Timed Interfaces, by Luca de Alfaro, Thomas A. Henzinger, Mariƫlle Stoelinga. EMSOFT 2002.

  11. Compositional Methods for Probabilistic Systems, by Luca de Alfaro, Thomas A. Henzinger, Ranjit Jhala. CONCUR 2001.

  12. Compositionality for Probabilistic Automata, by Nancy A. Lynch, Roberto Segala, Frits W. Vaandrager. CONCUR 2003.

  13. Compositional Security for Task-PIOAs, by R. Canetti, L. Cheung, D. Kaynar, N. Lynch, O. Pereira. CSF 2007.

  14. Switched PIOA: Parallel Composition via Distributed Scheduling, by L. Cheung, N. Lynch, R. Segala, and F. Vaandrager. TCS Vol. 365(1-2), 2006.

  15. Bisimulation can't be traced, by Bard Bloom, Sorin Istrail, Albert R. Meyer. JACM Vol.42(1), 1995.

  16. Towards a Mathematical Operational Semantics, by Daniele Turi, Gordon Plotkin. LICS'97.

  17. The Microcosm Principle and Concurrency in Coalgebra, by Ichiro Hasuo, Bart Jacobs, Ana Sokolova. Submitted preprint 2007.

  18. Compositionality for Markov reward chains with fast transitions, by Jasen Markovski, Ana Sokolova, Nikola Trcka, Erik de Vink. EPEW 2007.

  19. A Compacting Real-Time Memory Management System, by Silviu Craciunas, Christoph Kirsch, Hannes Payer, Ana Sokolova, Horst Stadler, Robert Staudinger. Submitted preprint 2007.

  20. Resource Management through System Call Scheduling, by Silviu Craciunas, Christoph Kirsch, Harald Roeck. Submitted preprint 2007.

Technical contact: Ana . Sokolova @ cs . uni-salzburg . at
Administrative contact: Petra . Kirchweger @ cs . uni-salzburg . at