3:30 p.m. - 5:00 p.m.
Applying Combinatorial Topology to Distributed Computing
21-02-11 (Lecture Series: 21, 22, 24 February 2011)
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.