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
Outline:
-
Introduction:
We introduce basic notions of combinatorial topology and how
they relate to models of distributed computing.
-
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.
-
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:
|