Distributed Computing Through Combinatorial Topology

Chapter 9

Manifold Protocols

Abstract

Theoretical distributed computing is primarily concerned with classifying tasks according to their difficulty. Which tasks can be solved in a given distributed computing model? We consider here two important tasks: set agreement and weak symmetry breaking. It turns out that the immediate snapshot protocols of Chapter 8 cannot solve these tasks. Moreover, we will identify a broader class of protocols called manifold protocols, that cannot solve -set agreement. (The impossibility proof for weak symmetry breaking is more complicated and is deferred to Chapter 12.)

Keywords

Moebius task; Sperner’s lemma; Chromatic ...