Topological Characterization of Stabilizing Consensus
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915019055169536 |
|---|---|
| author | Schmid, Ulrich Felber, Stephan Rincon-Galeana, Hugo |
| author_facet | Schmid, Ulrich Felber, Stephan Rincon-Galeana, Hugo |
| contents | We provide a complete characterization of the solvability/impossibility of deterministic stabilizing consensus in any computing model with benign process and communication faults using point-set topology. Relying on the topologies for infinite executions introduced by Nowak, Schmid and Winkler (JACM, 2024) for terminating consensus, we prove that semi-open decision sets and semi-continuous decision functions as introduced by Levin (AMM, 1963) are the appropriate means for this characterization: Unlike the decision functions for terminating consensus, which are continuous, semi-continuous functions do not require the inverse image of an open set to be open and hence allow to map a connected space to a disconnected one. We also show that multi-valued stabilizing consensus with weak and strong validity are equivalent, as is the case for terminating consensus. By applying our results to (variants of) all the known possibilities/impossibilities for stabilizing consensus, we easily provide a topological explanation of these results. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_07106 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Topological Characterization of Stabilizing Consensus Schmid, Ulrich Felber, Stephan Rincon-Galeana, Hugo Distributed, Parallel, and Cluster Computing General Topology C.2.4; F.1.1; G.m We provide a complete characterization of the solvability/impossibility of deterministic stabilizing consensus in any computing model with benign process and communication faults using point-set topology. Relying on the topologies for infinite executions introduced by Nowak, Schmid and Winkler (JACM, 2024) for terminating consensus, we prove that semi-open decision sets and semi-continuous decision functions as introduced by Levin (AMM, 1963) are the appropriate means for this characterization: Unlike the decision functions for terminating consensus, which are continuous, semi-continuous functions do not require the inverse image of an open set to be open and hence allow to map a connected space to a disconnected one. We also show that multi-valued stabilizing consensus with weak and strong validity are equivalent, as is the case for terminating consensus. By applying our results to (variants of) all the known possibilities/impossibilities for stabilizing consensus, we easily provide a topological explanation of these results. |
| title | Topological Characterization of Stabilizing Consensus |
| topic | Distributed, Parallel, and Cluster Computing General Topology C.2.4; F.1.1; G.m |
| url | https://arxiv.org/abs/2411.07106 |