The consensus number of a shift register equals its width
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910926611939328 |
|---|---|
| author | Aspnes, James |
| author_facet | Aspnes, James |
| contents | The consensus number of a w-bit register supporting logical left shift and right shift operations is exactly w, giving an example of a class of types, widely implemented in practice, that populates all levels of the consensus hierarchy. This result generalizes to w-wide shift registers over larger alphabets. In contrast, a register providing arithmetic right shift, which replicates the most significant bit instead of replacing it with zero, is shown to solve consensus for any fixed number of processes as long as its width is at least two. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_01691 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The consensus number of a shift register equals its width Aspnes, James Distributed, Parallel, and Cluster Computing F.2.2 The consensus number of a w-bit register supporting logical left shift and right shift operations is exactly w, giving an example of a class of types, widely implemented in practice, that populates all levels of the consensus hierarchy. This result generalizes to w-wide shift registers over larger alphabets. In contrast, a register providing arithmetic right shift, which replicates the most significant bit instead of replacing it with zero, is shown to solve consensus for any fixed number of processes as long as its width is at least two. |
| title | The consensus number of a shift register equals its width |
| topic | Distributed, Parallel, and Cluster Computing F.2.2 |
| url | https://arxiv.org/abs/2505.01691 |