History-Independent Concurrent Objects
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866913434929463296 |
|---|---|
| author | Attiya, Hagit Bender, Michael A. Farach-Colton, Martin Oshman, Rotem Schiller, Noa |
| author_facet | Attiya, Hagit Bender, Michael A. Farach-Colton, Martin Oshman, Rotem Schiller, Noa |
| contents | A data structure is called history independent if its internal memory representation does not reveal the history of operations applied to it, only its current state. In this paper we study history independence for concurrent data structures, and establish foundational possibility and impossibility results. We show that a large class of concurrent objects cannot be implemented from smaller base objects in a manner that is both wait-free and history independent; but if we settle for either lock-freedom instead of wait-freedom or for a weak notion of history independence, then at least one object in the class, multi-valued single-reader single-writer registers, can be implemented from smaller base objects, binary registers.
On the other hand, using large base objects, we give a strong possibility result in the form of a universal construction: an object with $s$ possible states can be implemented in a wait-free, history-independent manner from compare-and-swap base objects that each have $O(s + 2^n)$ possible memory states, where $n$ is the number of processes in the system. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_14445 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | History-Independent Concurrent Objects Attiya, Hagit Bender, Michael A. Farach-Colton, Martin Oshman, Rotem Schiller, Noa Distributed, Parallel, and Cluster Computing A data structure is called history independent if its internal memory representation does not reveal the history of operations applied to it, only its current state. In this paper we study history independence for concurrent data structures, and establish foundational possibility and impossibility results. We show that a large class of concurrent objects cannot be implemented from smaller base objects in a manner that is both wait-free and history independent; but if we settle for either lock-freedom instead of wait-freedom or for a weak notion of history independence, then at least one object in the class, multi-valued single-reader single-writer registers, can be implemented from smaller base objects, binary registers. On the other hand, using large base objects, we give a strong possibility result in the form of a universal construction: an object with $s$ possible states can be implemented in a wait-free, history-independent manner from compare-and-swap base objects that each have $O(s + 2^n)$ possible memory states, where $n$ is the number of processes in the system. |
| title | History-Independent Concurrent Objects |
| topic | Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2403.14445 |