Hits:

Indexed by:Journal Papers

Date of Publication:2020-05-01

Journal:MATHEMATICS

Included Journals:SCIE

Volume:8

Issue:5

Key Words:distributed computing; asynchronous computability; solo model; solvability; combinatorial topology

Abstract: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.