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

Outline:

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:

• Introduction (Slides (PPTX), Lecture notes (PDF))

• Topology (Slides (PPTX), Lecture notes (PDF))

• Manifolds (Slides (PPTX), Lecture notes (PDF))

• Connectivity (Slides (PPTX), Lecture notes (PDF))