Applications of Shellable Complexes to Distributed Computing

Date: Thursday, May 19, 2011
Speaker: Maurice Herlihy
Venue: IST Austria

Mondi 2

A simplicial complex is shellable if it can be constructed by gluing a sequence of n-simplexes to one another along (n-1)-faces only. Shellable complexes have been well-studied in combinatorial topology because they have many nice properties.

We show that many standard models of concurrent computation can be captured either as shellable complexes, or as the simple union of shellable complexes. We exploit their common shellability structure to derive new and remarkably succinct tight (or nearly so) lower bounds on connectivity of protocol complexes and hence on solutions to tasks such as k-set agreement.

This talk does not assume prior familiarity with Distributed Computing or Combinatorial Topology.

Joint work with Sergio Rajsbaum.

Posted in RiSE Seminar