Applications of Shellable Complexes to Distributed Computing (Invited Talk)

摘要

This talk describes recent Joint work with Sergio Rajsbaum [3].rnFor models of concurrent computation in which processes may fail by crash-ing, each possible computation can be characterized as a simplicial complex, a geometric structure constructed by "gluing together" simplexes in a regular manner [6]. Informally, a complex is κ-connected if it has no "holes" in dimen-sion k or lower. It is known that if the complex corresponding to every such computation is κ-connected, then one cannot solve (κ+ l)-set agreement [4,5,6].