Abstract:

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 with Sergio Rajsbaum.




Refreshments served from 14:15 on,
 	Lecture starts at 14:30
==================================