Maurice Herlihy received an A.B. degree in Mathematics from Harvard University and a Ph.D. degree in Computer Science from MIT. He has been an Assistant Professor in the Computer Science Department at Carnegie Mellon University, a member of the research staff at Digital Equipment Corporation’s Cambridge (MA) Research Lab, and a consultant for Sun Microsystems. He is now a Professor of Computer Science at Brown University.

Prof. Herlihy’s research centers on practical and theoretical aspects of multiprocessor synchronization, with a focus on wait-free and lock-free synchronization. His 1991 paper “Wait-Free Synchronization” won the 2003 Dijkstra Prize in Distributed Computing, and he shared the 2004 Goedel Prize for his 1999 paper “The Topological Structure of Asynchronous Computation.” He is a Fellow of the ACM.

 

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.