Loop agreement is a family of wait-free tasks that includes set agreement and simplex agreement, and was used to prove the undecidability of wait-free solvability of distributed tasks by read write memory. Herlihy and Rajsbaum defined the algebraic signature of a loop agreement task, which consists of a group and a distinguished element. They used the algebraic signature to characterize the relative power of loop agreement tasks. In particular, they showed that one task implements another exactly when there is a homomorphism between their respective signatures sending one distinguished element to the other. In this paper, we extend the previous result by defining the composition of multiple loop agreement tasks to create a new one with the same combined power. We generalize the original algebraic characterization of relative power to compositions of tasks. In this way, we can think of loop agreement tasks in terms of their basic building blocks. We also investigate a category-theoretic perspective of loop agreement by defining a category of loops, showing that the algebraic signature is a functor, and proving that our definition of task composition is the "correct" one, in a categorical sense.
Loop agreement has also been generalized to higher dimensions. Liu, Xu, and Pan define @cite_13 , where processes begin on distinguished vertices of an embedded @math -sphere of an @math -dimensional complex, and converge on a simplex of the embedded sphere. They generalize the algebraic signature characterization to a subclass of rendezvous tasks called rendezvous tasks, which are tasks whose output complexes have trivial homology groups below and above dimension @math , and a free Abelian @math -th homology group. The authors apply their main result to show there are countably infinite inequivalent nice rendezvous tasks.
@cite_13
2162458446
The rendezvous is a type of distributed decision tasks including many well-known tasks such as set agreement, simplex agreement, and approximation agreement. An n-dimensional rendezvous task, n>=1, allows n+2 distinct input values, and each execution produces at most n+2 distinct output values. A rendezvous task is said to implement another if an instance of its solution, followed by a protocol based on shared read write registers, solves the other. The notion of implementation induces a classification of rendezvous tasks of every dimension: two tasks belong to the same class if they implement each other. Previous work on classifying rendezvous tasks only focused on 1-dimensional ones. This paper solves an open problem by presenting the classification of nice rendezvous of arbitrary dimension. An n-dimensional rendezvous task is said to be nice if the qth reduced homology group of its decision space is trivial for q n, and free for q=n. Well-known examples are set agreement, simplex agreement, and approximation agreement. Each n-dimensional rendezvous task is assigned an algebraic signature, which consists of the nth homology group of the decision space, as well as a distinguished element in the group. It is shown that an n-dimensional nice rendezvous task implements another if and only if there is a homomorphism from its signature to that of the other. Hence the computational power of a nice rendezvous task is completely characterized by its signature. In each dimension, there are infinitely many classes of rendezvous tasks, and exactly countable classes of nice ones. A representative is explicitly constructed for each class of nice rendezvous tasks.