Loading...
Please wait, while we are loading the content...
Similar Documents
Asynchronous Computability Theorem in Arbitrary Solo Models
| Content Provider | MDPI |
|---|---|
| Author | Yue, Yunguang Lei, Fengchun Liu, Xingwu Wu, Jie |
| Copyright Year | 2020 |
| Description | In this paper, we establish the asynchronous computability theorem in d-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, a d-solo system allows as many d processes 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 a d-nest structure. As a byproduct, we find an alternative way to distinguish the computational power of d-solo objects for different d. |
| Starting Page | 757 |
| e-ISSN | 22277390 |
| DOI | 10.3390/math8050757 |
| Journal | Mathematics |
| Issue Number | 5 |
| Volume Number | 8 |
| Language | English |
| Publisher | MDPI |
| Publisher Date | 2020-05-10 |
| Access Restriction | Open |
| Subject Keyword | Mathematics Logic Distributed Computing Asynchronous Computability Solo Model Solvability Combinatorial Topology |
| Content Type | Text |
| Resource Type | Article |
