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 ...