(definition)
Definition: A data structure designed to work correctly while being accessed by many asynchronous threads. The two main types are blocking and nonblocking.
Generalization (I am a kind of ...)
data structure.
Note: Implementations must have correctness and liveness. Correctness means that it always behaves properly. Liveness means it eventually makes progress. This is in contrast to regular, sequential data structures that must have correctness but liveness is assumed.
Author: PEB
Mark Moir and Nir Shavit, Concurrent Data Structures. In Dinesh Metha and Sartaj Sahni (eds.), "Handbook of Data Structures and Applications", Chapman and Hall/CRC Press, Chapter 47, 2005.
Maurice Herlihy, Nir Shavit, Victor Luchangco, and Michael Spear, The Art of Multiprocessor Programming, 2nd Edition, 2021.
Wikipedia Concurrent data structure.
Armando Castañeda and Sergio Rajsbaum, Recent Advances on Principles of Concurrent Data Structures, Communications of the ACM, 67(8):45-46, doi: 10.1145/3653290
If you have suggestions, corrections, or comments, please get in touch with Paul Black.
Entry modified 20 September 2024.
HTML page formatted Fri Sep 20 10:36:59 2024.
Cite this as:
Paul E. Black, "concurrent data structure", in
Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 20 September 2024. (accessed TODAY)
Available from: https://www.nist.gov/dads/HTML/concurrentDataStructure.html