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

Concurrency (24h, 3 ECTS)

Course director: Emmanuel Haucourt

Time schedule (8x3h)

Teacher for 2018-2019

Emmanuel Haucourt ( professional web page)

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 for 2018-2019

  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 by default. However, questions asked in english will be answered in english.

Material

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

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.

Related courses

Semantics (2.2), Concurrent algorithms (2.18.2).

Prerequisites

It is useful, though not strictly necessary, to have attended courses (similar to) 1-15 (Semantics) and 1-16 (Concurrency).

Exams

To be annouced

Possible teachers

R. AmadioUniv. Paris DiderotPPS
E. GoubaultÉcole PolytechniqueLIX
E. HaucourtÉcole PolytechniqueLIX
J. LeiferINRIARocquencourt
E. LozesENS CachanLSV
F. ValenciaÉcole PolytechniqueLIX

Calendar 2018-2019

 
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