Distributed Computing Through Combinatorial Topology

Chapter 15

Classifying Loop Agreement Tasks

Abstract

Recall from Chapter 5, Section 5.6.2 that (colorless) loop agreement is a family of tasks for which the existence of a wait-free read-write protocol is undecidable. Here we give a complete classification of loop agreement tasks. Each loop agreement task can be assigned an algebraic signature consisting of a group and a distinguished element in . Remarkably, this signature completely characterizes ...