The evolution of non-degenerate and degenerate rendezvous tasks

摘要

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.