Asynchronous Computability Theorem in Arbitrary Solo Models

doi:10.3390/math8050757

	Asynchronous Computability Theorem in Arbitrary Solo Models
	Yue, Yunguang 1; Lei, Fengchun 1; Liu, Xingwu 1,2,3; Wu, Jie 4
	2020-05-01
发表期刊	MATHEMATICS
卷号	8 期号:5 页码:18
摘要	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.
关键词	distributed computing asynchronous computability solo model solvability combinatorial topology
DOI	10.3390/math8050757
收录类别	SCI
语种	英语
资助项目	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
WOS类目	Mathematics
WOS记录号	WOS:000542738100083
出版者	MDPI
引用统计	被引频次：3[WOS] [WOS记录] [WOS相关记录]
文献类型	期刊论文
条目标识符	http://119.78.100.204/handle/2XEOYT63/15153
专题	中国科学院计算技术研究所期刊论文_英文
通讯作者	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.