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)

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.

French and English

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

Plan of the Course and Material

Slides

Lecture 1

A QUICK OVERVIEW OF CONCURRENCY THEORY

PARALLEL AUTOMATA META LANGUAGE: Syntax, Control Flow Graph, Abstract Machine

CONSERVATIVE PROGRAMS: Potential Functions, Discrete Models

Lecture 2

AN ALGEBRAIC TOPOLOGY TEASER: Categories, Topology, Functors, Connectedness

METRIC SPACES: Functor terminology, Categories of metric spaces, Metric graphs

LOCALLY ORDERED METRIC GRAPHS: Partially ordered spaces, Ordered atlases, Basic properties, Ordered atlas on metric graphs

Lecture 3

GEOMETRIC MODELS: Cartesian product, From discrete to geometric models, Examples, Geometric vs Discrete, The motivating theorem

HOMOTOPY OF PATHS: Undirected case, Directed case, Relation to geometric models

INDEPENDANCE: Syntactical independence, Model independence, Observational independence, Comparison

Lecture 4

ISOTHETIC REGIONS: Boolean structure, Additional operators

FACTORING ISOTHETIC REGIONS: Free commutative monoids, Monoids of homogeneous languages, Homogeneous languages and isothetic regions

Lecture 5

FUNDAMENTAL CATEGORY: Abstract setting, Directed path functor, Natural congruences, Basic properties and computations

CATEGORY OF COMPONENTS: Motivation, Loop-free categories, Systems of weak isomorphisms, Construction, Properties, Examples, Finite connected loop-free categories

Videos

8 December 2020 part 1 / part 2 / part 3

15 December 2020 part 1 / part 2 / part 3 has not been recoreded...my fault :(

5 January 2021 part 1 / part 2 / part 3

12 January 2021 part 1 / part 2 / part 3

19 January 2021 part 1 / part 2 / part 3

26 January 2021 part 1 / part 2 / part 3

2 February 2021 part 1 / part 2 / part 3

9 February 2021 part 1 / part 2 / part 3

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).

Exam

2 March 2021, 9h00 - 12h00

Exam 2021

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