Distributed coordination problems from an abstract algebra point of view are examined in this paper. Loop agreement refers to a family of distributed coordination problems, or tasks, which includes set agreement and approximate agreement. The authors’ goal is to determine how to implement one loop agreement task in terms of another, and how to reduce this problem to a problem of abstract algebra.
The main reason loop agreement tasks are interesting to analyze is because they can generalize a number of distributed problems. There has been little underlying theory for such tasks, and this work attempts to fill that gap.
By assigning each loop agreement task an algebraic signature consisting of a finite group G and a distinguished element g in G, the authors prove that the task’s power (it’s ability to implement other tasks) can be determined. In particular, a task F with signature (M, m) implements a task H with signature (N, n) if and only if there exists a group homomorphism t:M->N carrying m to n.