A Wait-Free Classification of Loop Agreement Tasks

Maurice Herlihy
Computer Science Department
Brown University
Providence RI 02912
herlihy@cs.brown.edu

Sergio Rajsbaum
Instituto de Matemáticas
U.N.A.M.
Mexico City, D.F. 04510, Mexico
rajsbaum@math.unam.mx

Abstract

Loop agreement is a family of wait-free tasks that includes set agreement and approximate agreement tasks. This paper presents a complete classification of loop agreement tasks. Each loop agreement task can be assigned an algebraic signature consisting of a finitely-presented group G and a distinguished element g in G. This signature completely characterizes the task's computational power. If G and H are loop agreement tasks with respective signatures (G,g) and (H,h), then G implements H if and only if there exists a group homomorphism from G to H carrying g to h.