论文成果
The evolution of non-degenerate and degenerate rendezvous tasks
- 点击次数：
- 论文类型：期刊论文
- 发表时间：2019-09-01
- 发表刊物：TOPOLOGY AND ITS APPLICATIONS
- 收录刊物：SCIE
- 文献类型：J
- 卷号：264
- 页面范围：187-200
- ISSN号：0166-8641
- 关键字：Distributed computing; Rendezvous; Computability; Classification
- 摘要：In this paper, we weaken the nice condition of an n-dimensional rendezvous task defined in the work of X. Liu et al [11]. Then we introduce the definition of evolution of non-degenerate n-dimensional rendezvous task. A non-degenerate n-rendezvous task is said to be evolution if the q-th reduced homology group of its decision space is abelian group for q = n and trivial for the others. Well-known examples are set agreement, simplex agreement, and approximation agreement and so on. Each n-rendezvous task is assigned an algebraic signature, which consists of n-th homology group of the decision space, as well as a distinguished element in the group. We show that an evolution of non-degenerate n-dimensional rendezvous task implements another if and only if there is a homomorphism from its signature to the other. Hence the computational power of evolution of non-degenerate rendezvous task is completely characterized by its signature. Last, we talk about the degenerate n-dimensional rendezvous task in which the output values in any execution can construct at most an n-dimensional simplex. (C) 2019 Elsevier B.V. All rights reserved.
