Distributed Computing through Combinatorial Topology

Explore distributed computing through the lens of combinatorial topology in this lecture from the Hausdorff Trimester Program on Applied and Computational Algebraic Topology. Delve into how models and techniques from classical combinatorial algebraic topology have led to new lower bounds and impossibility results in distributed and concurrent computation. Learn about fundamental concepts and their application to a simple distributed problem. Cover topics such as communication rounds, reliable communication, muddy children problem, colorless tasks, shared read-write memory, asynchronous failures, configurations, executions, binary consensus, colorless layered protocols, input complexes, carrier maps, task specifications, protocol complex evolution, lower bound strategies, barycentric subdivision, compositions, and the fundamental theorem of distributed computing.

Distributed Computing through Combinatorial Topology
One Communication Round
Reliable Communication?
Muddy Children
Operational Explanation
Informal Task Definition
They Communicate
Colorless Tasks
Shared Read-Write Memory
Asynchronous Failures
Configurations
Executions
Crashes are implicit
Example: Binary Consensus
Colorless Layered Protocol
Input Complex for Binary Consensus
Carrier Map for Consensus
Task Specification
Round Zero Protocol Complex
Single Input: Round One
Protocol Complex: Round One
Protocol Complex Evolution
Lower Bound Strategy
Consensus Example
Barycentric Subdivision
Compositions
Fundamental Theorem
Proof Outline