点击次数：

论文类型：期刊论文

发表时间：2019-09-01

发表刊物：TOPOLOGY AND ITS APPLICATIONS

收录刊物：SCIE

卷号：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.