Classifying rendezvous tasks of arbitrary dimension
Classifying rendezvous tasks of arbitrary dimension
复制标题
对任意维度的集合任务进行分类
DOI：
10.1016/j.tcs.2009.01.033
复制
发表时间：
2009-05
期刊：
影响因子：
--
通讯作者：
中科院分区：
文献类型：
--
作者：
交会是一种分布式决策任务，包括集合协议、单纯形协议、近似协议等许多常见的决策任务。N维集合任务n≥1允许n+2个不同的输入值，每次执行最多产生n+2个不同的输出值。如果一个集合任务的解决方案的一个实例，然后是一个基于共享读/写寄存器的协议解决了另一个问题，则称为实现另一个任务。实现的概念归纳了每个维度的集合任务的分类：如果两个任务彼此实现，则它们属于同一类。以前关于交会任务分类的工作只集中在一维任务上。本文通过给出任意维好交会的分类，解决了一个公开问题。如果一个n维交会任务的决策空间的第q个约化同调群对于q≠n是平凡的，并且对于q=n是自由的，则称它是好的。著名的例子有集合一致、单纯形一致和近似一致。每个n维交会任务被分配一个代数签名，它由决策空间的第n个同调群组成，以及该组中的一个可区分元素。证明了n维好交会任务实现另一个任务的充要条件是它的签名与另一个任务的签名同态。因此，一个好的交会任务的计算能力完全取决于它的签名。在每个维度中，都有无限多个交会任务类，以及恰好可数的几个好任务类。为每一类良好的会合任务明确地构造了一个代表。
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.
登录
查看更多内容
DOI：
10.1007/11780823_1
发表时间：
2006-07
期刊：
--
影响因子：
--
作者：
E. Kranakis;D. Krizanc;S. Rajsbaum
通讯作者：
E. Kranakis;D. Krizanc;S. Rajsbaum
DOI：
10.1007/3-540-56188-9
发表时间：
1992
期刊：
--
影响因子：
--
作者：
Seif Haridi
通讯作者：
Seif Haridi
DOI：
10.1145/114005.102808
发表时间：
1991-01-01
影响因子：
1.3
作者：
HERLIHY, M
通讯作者：
HERLIHY, M
DOI：
10.1016/j.tcs.2008.02.010
发表时间：
2006-07
期刊：
--
影响因子：
--
作者：
D. Kowalski;Adam Malinowski
通讯作者：
D. Kowalski;Adam Malinowski
DOI：
10.1145/259380.259440
发表时间：
1997-08
期刊：
--
影响因子：
--
作者：
G. Hoest;N. Shavit
通讯作者：
G. Hoest;N. Shavit