Parisian Master of Research in Computer Science
Master Parisien de Recherche en Informatique (MPRI)

Concurrency (24h, 3 ECTS)

Course director: Emmanuel Haucourt

Academic year 2020 - 2021

Teacher

Emmanuel Haucourt ( professional web page)

Due to containment, I still do not know how the first courses will be organized: recorded videos with live sessions for questions / live sessions only / on site as usual (extremely unlikely).

Goals

Starting from a restriction of the language introduced by E. W. Dijkstra, we explain how directed algebraic topology can be applied to the study of concurrency.

Plan of the course

  1. What kind of concurrency in this course?
  2. Restricted Dijkstra PV language
  3. Precubical sets as a generalization of graphs
  4. Control-flow graph, conservative programs, and precubical control flow
  5. Locally ordered spaces
  6. Directed realization of graphs and precubical sets
  7. Isothetic regions
  8. The fundamental category
  9. Seifert and van Kampen theorem for the fundamental category [optional]
  10. The category of components
  11. Factorization
  12. Some other topological models

French and English

French. However, questions asked in english will be answered in english.

Material

Slides and (rather obsolete) lecture notes can be found here.

Recorded videos (?) Link to «Zoom» / «Big Blue Button» rooms (?).

Bibliography

Books

  • Fajstrup, L., Goubault, É., Haucourt, E., Mimram, S., and Raußen, M.
    Directed Algebraic Topology and Concurrency. Springer 2016.
  • Brown, R. Topology and Groupoids. BookSurge. 2006.
  • Higgins, P. J. Categories and Groupoids. Van Nostrand-Reinhold 1975.
  • Hansen, P. B. The Origin of Concurrent Programming:
    From Semaphores to Remote Procedure Calls
    . Springer 2002.

Articles

  • Dijkstra, E. W. Cooperating Sequential Processes. In Genuys, F. (ed.)
    Programming Languages: NATO Advanced Study Institute. Academic Press 1968.
  • Fajstrup, L., Goubault, É., and Raußen, M. Algebraic Topology and Concurrency.
    Theoretical Computer Science 357(1):241–278 2006.
    Presented at Mathematical Foundations of Computer Science in 1998 (London).

Basic Category Theory

  • Awodey, S. Category Theory. Clarendon Press. Oxford 2006.
  • Leinster, T. Basic Category Theory. Cambridge University Press 2014.
  • Roman, S. An Introduction to the Language of Category theory. Birkhäuser 2017.

More advanced books:

  • Mac Lane, S. Categories for the Working Mathematician (2nd ed.). Springer 1998.
  • Riehl, E. Category Theory in Context. Dover 2016.

Related courses

Models of programming languages: domains, categories, and games (2.2), Distributed algorithms on shared memory (2.18.2).

Exams

To be annouced

Calendar and Time Schedule

Second period 12h45 - 15h45 :
8, 15 december 2020,
5, 12, 19, 26 january 2021,
2, 9 february 2021

 
Universités partenaires Université Paris-Diderot
Université Paris-Saclay
ENS Cachan École polytechnique Télécom ParisTech
ENS
Établissements associés Université Pierre-et-Marie-Curie CNRS INRIA CEA