The Asynchronous Computability Theorem

The Asynchronous Computability Theorem, a talk delivered by Hei Li on 19th January 2022 at Churchill College, Cambridge Consensus cannot be achieved in an asynchronous wait-free model, but how could we prove this result? In this talk, we will explore a surprising connection between protocols for distributed systems and concepts in algebraic topology. This provides us with a concise mathematical framework unifying many classical concurrency models, enabling us to reason about concurrency via static combinatorial structures. For this talk, we will use this connection to prove that consensus is impossible in an asynchronous wait-free model.