The Asynchronous Computability Theorem

Add to your list(s) Download to your calendar using vCal

• Hei Li, Churchill College
• Wednesday 19 January 2022, 19:00-19:30
• Wolfson Hall, Churchill College.

If you have a question about this talk, please contact Matthew Ireland.

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.

This talk is part of the Churchill CompSci Talks series.

This talk is included in these lists:

• Churchill CompSci Talks
• Wolfson Hall, Churchill College
• computer science
• se393's list

Note that ex-directory lists are not shown.