点击次数：

论文类型：期刊论文

发表时间：2020-05-01

发表刊物：MATHEMATICS

收录刊物：SCIE

卷号：8

期号：5

关键字：distributed computing; asynchronous computability; solo model; solvability; combinatorial topology

摘要：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.