Name
Abstract | ||
|---|---|---|
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 qn, 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. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1016/j.tcs.2009.01.033 | Theor. Comput. Sci. |
Keywords | DocType | Volume |
rendezvous task,approximation agreement,Computability,nice rendezvous,simplex agreement,arbitrary dimension,decision space,Classifying rendezvous task,Rendezvous,Classification,Loop agreement,n-dimensional nice rendezvous task,decision task,nice rendezvous task,classifying rendezvous task,n-dimensional rendezvous task,Distributed computing | Journal | 410 |
Issue | ISSN | Citations |
21-23 | Theoretical Computer Science | 3 |
PageRank | References | Authors |
0.38 | 15 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Xingwu Liu | 1 | 19 | 12.77 |
| Zhiwei Xu | 2 | 1563 | 162.88 |
| Jianzhong Pan | 3 | 3 | 0.72 |