中国科学院机构知识库网格
Chinese Academy of Sciences Institutional Repositories Grid
首页 机构 成果 学者
  
  1. CAS IR Grid
  2. 计算技术研究所
  3. 中国科学院计算技术研究所
  4. 中国科学院计算技术研究所期刊论文
  5. 英文
Classifying rendezvous tasks of arbitrary dimension

文献类型：期刊论文

作者Liu, Xingwu1; Xu, Zhiwei1; Pan, Jianzhong2
刊名THEORETICAL COMPUTER SCIENCE
出版日期2009-05-17
卷号410期号:21-23页码:2162-2173
关键词Distributed computing Loop agreement Rendezvous Computability Classification
ISSN号0304-3975
DOI10.1016/j.tcs.2009.01.033
英文摘要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.
资助项目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记录号WOS:000266178200021
出版者ELSEVIER SCIENCE BV
源URL[http://119.78.100.204/handle/2XEOYT63/11896]  
专题中国科学院计算技术研究所期刊论文_英文
通讯作者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.

入库方式： OAI收割

来源：计算技术研究所

浏览0
下载0
收藏0
其他版本

除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。