The Asynchronous Computability Theorem - A Marriage Between Distributed Systems and Algebraic Topology

Status: Completed
Year: 2022

Abstract

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.

Context

In the second year of my undergrads, I shattered three of my teeth after fainting in the middle of the streets without warning. After enduring a horrible half a year, I finally received my implants in 2021 December! And as everyone knows, there is no better way to celebrate the occassion of getting one’s teeth back than to actually use them…thus the talk. The slides for the talk can be found here. The talk was recorded and uploaded to Youtube.