Главная
Study mode:
on
1
Distributed Computing through Combinatorial Topology
2
One Communication Round
3
Reliable Communication?
4
Muddy Children
5
Operational Explanation
6
Informal Task Definition
7
They Communicate
8
Colorless Tasks
9
Shared Read-Write Memory
10
Asynchronous Failures
11
Configurations
12
Executions
13
Crashes are implicit
14
Example: Binary Consensus
15
Colorless Layered Protocol
16
Input Complex for Binary Consensus
17
Carrier Map for Consensus
18
Task Specification
19
Round Zero Protocol Complex
20
Single Input: Round One
21
Protocol Complex: Round One
22
Protocol Complex Evolution
23
Lower Bound Strategy
24
Consensus Example
25
Barycentric Subdivision
26
Compositions
27
Fundamental Theorem
28
Proof Outline
Description:
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

Hausdorff Center for Mathematics
Add to list