TY - GEN

T1 - History-Independent Concurrent Objects

AU - Attiya, Hagit

AU - Bender, Michael A.

AU - Farach-Colton, Martín

AU - Oshman, Rotem

AU - Schiller, Noa

N1 - Publisher Copyright:
© 2024 Association for Computing Machinery. All rights reserved.

PY - 2024/6/17

Y1 - 2024/6/17

N2 - 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 + 2n) possible memory states, where n is the number of processes in the system.

AB - 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 + 2n) possible memory states, where n is the number of processes in the system.

KW - multi-valued register

KW - queue

KW - state-quiescent history independence

KW - universal implementation

UR - http://www.scopus.com/inward/record.url?scp=85199028353&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85199028353&partnerID=8YFLogxK

U2 - 10.1145/3662158.3662814

DO - 10.1145/3662158.3662814

M3 - Conference contribution

AN - SCOPUS:85199028353

T3 - Proceedings of the Annual ACM Symposium on Principles of Distributed Computing

SP - 14

EP - 24

BT - PODC 2024 - Proceedings of the 2024 ACM Symposium on Principles of Distributed Computing

PB - Association for Computing Machinery

T2 - 43rd ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, PODC 2024

Y2 - 17 June 2024 through 21 June 2024

ER -