Specifying Relaxed Concurrent Data Structures Using NADTs
Journal of Computing and Information Technology · 30.01.2026 · 33 (4) · 219
DOI: 10.20532/cit.2025.1006091 ↗Kurz gefasst
Fachartikel in der Zeitschrift Journal of Computing and Information Technology, online erschienen am 30.01.2026. Verfasst von Jie Peng und 1 weiteren Autor:innen.
Abstract (Originalsprache)
To improve performance scalability of concurrent data structures, one solution is to relax their sequential semantics. While a variety of specification approaches focus on characterizing the relaxed semantics, client-side reasoning using the current methodologies is difficult. We employ nondeterministic abstract data types (NADTs) for the first time to specify the relaxed concurrent data structures, and as instantiations of our specification approach, we propose new correctness criteria of out-of-order queues and stacks. We further prove the relaxation equivalence of the out-of-order dequeue and enqueue operations. Our specification approach is intuitive and generic, and can provide clients with explicit interfaces. As a demonstration of our approach, we specify and verify the k-segment queue.
Zitieren
APA
Peng, J., & Wen, T. (2026). Specifying Relaxed Concurrent Data Structures Using NADTs. Journal of Computing and Information Technology, 33(4), 219. https://doi.org/10.20532/cit.2025.1006091
Vancouver
Peng J, Wen T. Specifying Relaxed Concurrent Data Structures Using NADTs. Journal of Computing and Information Technology. 2026;33(4):219. doi:10.20532/cit.2025.1006091
BibTeX
@article{Peng2026,
author = {Peng, Jie and Wen, Tangliu},
title = {Specifying Relaxed Concurrent Data Structures Using NADTs},
journal = {Journal of Computing and Information Technology},
year = {2026},
volume = {33},
number = {4},
pages = {219},
doi = {10.20532/cit.2025.1006091}
}
EUVIMED