Asynchronous Computability Theorem in Arbitrary Solo Models

doi:10.3390/math8050757

CORC > 计算技术研究所 > 中国科学院计算技术研究所 > 中国科学院计算技术研究所期刊论文 > 英文

	Asynchronous Computability Theorem in Arbitrary Solo Models
	Yue, Yunguang 1; Lei, Fengchun 1; Liu, Xingwu 1,2,3; Wu, Jie 4
刊名	MATHEMATICS
	2020-05-01
卷号	8 期号:5 页码:18
关键词	distributed computing asynchronous computability solo model solvability combinatorial topology
DOI	10.3390/math8050757
英文摘要	In this paper, we establish the asynchronous computability theorem ind-solo system by borrowing concepts from combinatorial topology, in which we state a necessary and sufficient conditions for a task to be wait-free computable in that system. Intuitively, ad-solo system allows as manydprocesses to access it as if each were running solo, namely, without detecting communication from any peer. As an application, we completely characterize the solvability of the input-less tasks in such systems. This characterization also leads to a hardness classification of these tasks according to whether their output complexes hold ad-nest structure. As a byproduct, we find an alternative way to distinguish the computational power ofd-solo objects for differentd.
资助项目	Key-Area Research and Development Program of Guangdong Province[2020B010164003] ; Natural Science Foundation of China[11971144] ; High-level Scientific Research Foundation of Hebei Province ; National Natural Science Foundation of China[61702480] ; Youth Innovation Promotion Association of Chinese Academy of Sciences[2013073] ; State Key Laboratory of Computer Architecture Open Fund[CARCH3410]
WOS研究方向	Mathematics
语种	英语
出版者	MDPI
WOS记录号	WOS:000542738100083
内容类型	期刊论文
源URL	[http://119.78.100.204/handle/2XEOYT63/15152]
专题	中国科学院计算技术研究所期刊论文_英文
通讯作者	Lei, Fengchun
作者单位	1.Dalian Univ Technol, Sch Math Sci, Dalian 116024, Peoples R China 2.Chinese Acad Sci, ICT, SKL Comp Architecture, Beijing 100049, Peoples R China 3.Univ Chinese Acad Sci, Sch Comp Sci & Technol, Beijing 100049, Peoples R China 4.Hebei Normal Univ, Coll Math Sci, Shijiazhuang 050024, Hebei, Peoples R China
推荐引用方式 GB/T 7714	Yue, Yunguang,Lei, Fengchun,Liu, Xingwu,et al. Asynchronous Computability Theorem in Arbitrary Solo Models[J]. MATHEMATICS,2020,8(5):18.
APA	Yue, Yunguang,Lei, Fengchun,Liu, Xingwu,&Wu, Jie.(2020).Asynchronous Computability Theorem in Arbitrary Solo Models.MATHEMATICS,8(5),18.
MLA	Yue, Yunguang,et al."Asynchronous Computability Theorem in Arbitrary Solo Models".MATHEMATICS 8.5(2020):18.