book

Distributed Computing Through Combinatorial Topology

by Maurice Herlihy, Dmitry Kozlov, Sergio Rajsbaum

November 2013

Intermediate to advanced

336 pages

9h 56m

English

Morgan Kaufmann

Read now

Unlock full access

Companion Site
Abstract1.1 Concurrency everywhere1.2 Distributed computing1.3 Two classic distributed computing problems1.4 Chapter notes1.5 Exercises
Abstract2.1 Elementary graph theory2.2 Tasks2.3 Models of computation2.4 Approximate agreement2.5 Two-process task solvability2.6 Chapter notes2.7 Exercises

Abstract3.1 Basic concepts3.2 Simplicial complexes3.3 Standard constructions3.4 Carrier maps3.5 Connectivity3.6 Subdivisions3.7 Simplicial and continuous approximations3.8 Chapter notes3.9 Exercises
Abstract4.1 Operational model4.2 Combinatorial model4.3 The computational power of wait-free colorless immediate snapshots4.4 Chapter notes4.5 Exercises
Abstract5.1 Overview of models5.2 t-Resilient layered snapshot protocols5.3 Layered snapshots with k-set agreement5.4 Adversaries5.5 Message-passing protocols5.6 Decidability5.7 Chapter notes5.8 Exercises
Abstract6.1 Byzantine failures6.2 Byzantine communication abstractions6.3 Byzantine set agreement6.4 Byzantine barycentric agreement6.5 Byzantine task solvability6.6 Byzantine shared memory6.7 Chapter notes6.8 Exercises
Abstract7.1 Motivation7.2 Combinatorial setting7.3 Applications7.4 BG simulation7.5 Conclusions7.6 Chapter notes7.7 Exercises
Abstract8.1 Overview8.2 Tasks8.3 Examples of tasks8.4 Protocols8.5 Chapter notes8.6 Exercises
Abstract9.1 Manifold protocols9.2 Layered immediate snapshot protocols9.3 No set agreement from manifold protocols9.4 Set agreement vs. weak symmetry breaking9.5 Chapter notes9.6 Exercises
Abstract10.1 Consensus and path connectivity10.2 Immediate snapshot model and connectivity10.3 k-Set agreement and (k-1)-connectivity10.4 Immediate snapshot model and k-connectivity10.5 Chapter notes10.6 Exercises
Abstract11.1 Inherently colored tasks: the hourglass task11.2 Solvability for colored tasks11.3 Algorithm implies map11.4 Map implies algorithm11.5 A sufficient topological condition11.6 Chapter notes11.7 Exercises
Abstract12.1 An upper bound: renaming with 2n+1 names12.2 Weak symmetry breaking12.3 The index lemma12.4 Binary colorings12.5 A lower bound for 2n -renaming12.6 Chapter notes12.7 Exercises
Abstract13.1 Shellability13.2 Examples13.3 Pseudospheres13.4 Carrier maps and shellable complexes13.5 Applications13.6 Chapter notes13.7 Exercises
Abstract14.1 Model14.2 Shared-memory models14.3 Trivial reductions14.4 Layered snapshot from read-write14.5 Immediate snapshot from snapshot14.6 Immediate snapshot from layered immediate snapshot14.7 Snapshot from layered snapshot14.8 Chapter Notes14.9 Exercises
Abstract15.1 The fundamental group15.2 Algebraic signatures15.3 Main theorem15.4 Applications15.5 Torsion classes15.6 Conclusions15.7 Chapter notes15.8 Exercises
Abstract16.1 A glimpse of discrete geometry16.2 Chapter notes16.3 Exercises