Chennai Mathematical Institute

Lecture Series

Applying Combinatorial Topology to Distributed Computing

Professor Maurice Herlihy from Brown University will offer a three lecture mini-course on Applying Combinatorial Topology to Distributed Computing from February 21–24, 2011. All lectures will be held in the Seminar Hall at CMI.

Lecture schedule

  • Dates : Monday 21 February, Tuesday 22 February, Thursday 24 February

  • Time : 3:30 pm–5:00 pm


  1. Introduction:

    We introduce basic notions of combinatorial topology and how they relate to models of distributed computing.

  2. Manifolds, Impossibility, and Separation:

    We show how to use topological techniques to derive a simple impossibility result, showing that one cannot construct a protocol for the set agreement task in the round-by-round immediate snapshot model of computation.

  3. Connectivity and set agreement:

    Informally, a complex is "k-connected" if it has "no holes" in dimension k and lower. We show that certain kinds of sychronization tasks are impossible any models of computation associated with k-connected complexes. We conclude with a brief survey of open problems.

Notes and slides: