Chapter 4

Colorless Wait-Free Computation


We outline the basic connection between distributed computing and combinatorial topology in terms of two formal models: a conventional operational model, in which systems consist of communicating state machines whose behaviors unfold over time, and the combinatorial model, in which all possible behaviors are captured statically using topological notions. We start with one particular system model (shared memory) and focus on a restricted (but important) class of problems (so-called “colorless” tasks).


Configurations; Executions; Layered executions; Layered protocols; Processes; Protocols; Schedules; Tasks

We saw in Chapter 2 that we can construct a combinatorial theory of two-process distributed ...

Get Distributed Computing Through Combinatorial Topology now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.