Continuous Tasks and the Asynchronous Computability Theorem
summary
Proves an iff characterization: a distributed task is wait-free shared-memory solvable exactly when there exists a continuous chromatic function carried by the task’s carrier map. Delivers a constructive chromatic approximation theorem (color-preserving subdivision and simplicial map), extends the Asynchronous Computability Theorem to continuous tasks, and shows how to design consensus preference approximate agreement maps that control the fraction of exact agreements. Provides explicit subdivisions and induction proofs and demonstrates the constructions succeed.
AI-written summary · about
chapters (27)
- 0:00Intro
- 0:18Overview
- 1:28Communication
- 1:55Synchrony Model
- 3:02Sequential vs Distributed Tasks
- 3:46Agreement Tasks
- 5:14Topology
- 5:39Simplices
- 6:08Abstract Simplicial Complex
- 6:34Simplicial Maps
- 6:59Geometric Simplicial Complex
- 7:42Subdivision
- 8:12Simplicial approximation
- 9:18Topological Modeling of Distributed Systems
- 10:11Example: 2-Process Wait-free Shared Memory
- 11:09Input Complex
- 13:56Protocol Complexes for Wait-free Shared Memory
- 15:26The Asynchronous Computability Theorem (ACT)
- 16:03Application Example: Consensus Impossibility
- 17:39The Hourglass Task
- 18:46The Hourglass Impossibility
- 20:03Example of Simplicial Neighborhoods
- 20:21Chromatic Functions
- 21:02The Chromatic Approximation Theorem
- 21:44A visual sketch of the proof (1/5)
- 24:07Continuous Tasks
- 25:03Consensus-preferent approximate agreement
related talks
01h 06mTransient: Unrestricted Algebraic and Monadic Composability
18mSureDistrib: Verifying Almost-Sure Termination of Composite Asynchronous Byzantine(…)
01h 11mA Programmable Cloud: CALM Foundations and Open Challenges
50mVerifying a distributed system with combinatorial topology
21mEnabling User-level Asynchronous Tasking in the FA-BSP Model - Case Study:(…)
01h 20mAn Introduction to Distributed, Massively Parallel, and Local Computation Algorithms
35mWhy Extension-Based Proofs Fail
26mOn the O(1/k) Convergence of the Asynchronous Distributed Alternating Direction Method of Mult...