The Power of Strong Linearizability: the Difficulty of Consistent Refereeing
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866914014917820416 |
|---|---|
| author | Attiya, Hagit Castañeda, Armando Enea, Constantin |
| author_facet | Attiya, Hagit Castañeda, Armando Enea, Constantin |
| contents | This paper studies the relation between agreement and strongly linearizable implementations of various objects. This leads to new results about implementations of concurrent objects from various primitives including window registers and interfering primitives. We consider implementations that provide both strong linearizability and decisive linearizability.
We identify that lock-free, respectively, wait-free, strongly linearizable implementations of several concurrent objects entail a form of agreement that is weaker than consensus but impossible to strongly-linearizable implement with combinations of non-universal primitives. In both cases, lock-free and wait-free, this form of agreement requires a distinguished process to referee a competition that involves all other processes. Our results show that consistent refereeing of such competitions (i.e. the outcome of the competition does not change in extensions of the current execution) requires high coordination power.
More specifically, two contest objects are defined and used to capture the power of strong linearizability in lock-free and wait-free implementations, respectively. Both objects are strictly weaker than consensus, in the sense that they have a wait-free linearizable (in fact, decisively linearizable) implementation from reads and writes. The contest objects capture strong linearizability since (1) they have strongly linearizable implementations from several ``high-level'' objects like queues, snapshots, counters, and therefore, impossibility results for them carry over to these objects, and (2) they admit powerful impossibility results for strong linearizability that involve window registers and interfering primitives, which are non-universal. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_18401 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The Power of Strong Linearizability: the Difficulty of Consistent Refereeing Attiya, Hagit Castañeda, Armando Enea, Constantin Distributed, Parallel, and Cluster Computing This paper studies the relation between agreement and strongly linearizable implementations of various objects. This leads to new results about implementations of concurrent objects from various primitives including window registers and interfering primitives. We consider implementations that provide both strong linearizability and decisive linearizability. We identify that lock-free, respectively, wait-free, strongly linearizable implementations of several concurrent objects entail a form of agreement that is weaker than consensus but impossible to strongly-linearizable implement with combinations of non-universal primitives. In both cases, lock-free and wait-free, this form of agreement requires a distinguished process to referee a competition that involves all other processes. Our results show that consistent refereeing of such competitions (i.e. the outcome of the competition does not change in extensions of the current execution) requires high coordination power. More specifically, two contest objects are defined and used to capture the power of strong linearizability in lock-free and wait-free implementations, respectively. Both objects are strictly weaker than consensus, in the sense that they have a wait-free linearizable (in fact, decisively linearizable) implementation from reads and writes. The contest objects capture strong linearizability since (1) they have strongly linearizable implementations from several ``high-level'' objects like queues, snapshots, counters, and therefore, impossibility results for them carry over to these objects, and (2) they admit powerful impossibility results for strong linearizability that involve window registers and interfering primitives, which are non-universal. |
| title | The Power of Strong Linearizability: the Difficulty of Consistent Refereeing |
| topic | Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2506.18401 |