3:30 p.m. - 5:00 p.m.
Applying Combinatorial Topology to Distributed Computing
Maurice Herlihy
Brown University.
21-02-11 (Lecture Series: 21, 22, 24 February 2011)

---

Abstract

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