Class Central is learner-supported. When you buy through links on our site, we may earn an affiliate commission.

YouTube

Distributed Computing through Combinatorial Topology

Hausdorff Center for Mathematics via YouTube

Overview

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.

Syllabus

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

Taught by

Hausdorff Center for Mathematics

Reviews

Start your review of Distributed Computing through Combinatorial Topology

Never Stop Learning.

Get personalized course recommendations, track subjects and courses with reminders, and more.

Someone learning on their laptop while sitting on the floor.