EUVIMEDEUVIMED entdecken
Crossref

Specifying Relaxed Concurrent Data Structures Using NADTs

Jie Peng, Tangliu Wen

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →