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
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: