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 -