Classifying rendezvous tasks of arbitrary dimension

doi:10.1016/j.tcs.2009.01.033

	Classifying rendezvous tasks of arbitrary dimension
	Liu, Xingwu 1; Xu, Zhiwei 1; Pan, Jianzhong 2
	2009-05-17
发表期刊	THEORETICAL COMPUTER SCIENCE
ISSN	0304-3975
卷号	410 期号:21-23 页码:2162-2173
摘要	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 not equal 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. (C) 2009 Elsevier B.V. All rights reserved.
关键词	Distributed computing Loop agreement Rendezvous Computability Classification
DOI	10.1016/j.tcs.2009.01.033
收录类别	SCI
语种	英语
资助项目	National Natural Science Foundation of China[60603004] ; National Natural Science Foundation of China[60803120] ; National Natural Science Foundation of China[60873243] ; China's National Basic Research and Development 973 Program[2005CB321807]
WOS研究方向	Computer Science
WOS类目	Computer Science, Theory & Methods
WOS记录号	WOS:000266178200021
出版者	ELSEVIER SCIENCE BV
引用统计	被引频次：9[WOS] [WOS记录] [WOS相关记录]
文献类型	期刊论文
条目标识符	http://119.78.100.204/handle/2XEOYT63/11897
专题	中国科学院计算技术研究所期刊论文_英文
通讯作者	Liu, Xingwu
作者单位	1.Chinese Acad Sci, Inst Comp Technol, Beijing 100864, Peoples R China 2.Chinese Acad Sci, Sch Math & Syst Sci, Beijing 100864, Peoples R China
推荐引用方式 GB/T 7714	Liu, Xingwu,Xu, Zhiwei,Pan, Jianzhong. Classifying rendezvous tasks of arbitrary dimension[J]. THEORETICAL COMPUTER SCIENCE,2009,410(21-23):2162-2173.
APA	Liu, Xingwu,Xu, Zhiwei,&Pan, Jianzhong.(2009).Classifying rendezvous tasks of arbitrary dimension.THEORETICAL COMPUTER SCIENCE,410(21-23),2162-2173.
MLA	Liu, Xingwu,et al."Classifying rendezvous tasks of arbitrary dimension".THEORETICAL COMPUTER SCIENCE 410.21-23(2009):2162-2173.