Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2303.14769 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909292427214848 |
|---|---|
| author | Shi, Yusong Liu, Weidong |
| author_facet | Shi, Yusong Liu, Weidong |
| contents | The concept of extension-based proofs models the idea of a valency argument, which is widely used in distributed computing. Extension-based proofs are limited in power: it has been shown that there is no extension-based proof of the impossibility of a wait-free protocol for $(n,k)$-set agreement among $n > k \geq 2$ processes. There are only a few tasks that have been proven to have no extension-based proof of the impossibility, since the techniques in these works are closely related to the specific task.
We give a necessary and sufficient condition for colorless tasks to have no extension-based proofs of the impossibility of wait-free protocols in the NIIS model. We introduce a general adversarial strategy decoupled from any concrete task specification. In this strategy, some properties of the chromatic subdivision that is widely used in distributed computing are proved. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2303_14769 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Colorless Tasks and Extension-Based Proofs Shi, Yusong Liu, Weidong Distributed, Parallel, and Cluster Computing The concept of extension-based proofs models the idea of a valency argument, which is widely used in distributed computing. Extension-based proofs are limited in power: it has been shown that there is no extension-based proof of the impossibility of a wait-free protocol for $(n,k)$-set agreement among $n > k \geq 2$ processes. There are only a few tasks that have been proven to have no extension-based proof of the impossibility, since the techniques in these works are closely related to the specific task. We give a necessary and sufficient condition for colorless tasks to have no extension-based proofs of the impossibility of wait-free protocols in the NIIS model. We introduce a general adversarial strategy decoupled from any concrete task specification. In this strategy, some properties of the chromatic subdivision that is widely used in distributed computing are proved. |
| title | Colorless Tasks and Extension-Based Proofs |
| topic | Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2303.14769 |