@article{ART003280249},
author={Yong-Joon Cho and Nai-Hoon Jung},
title={Time-Stamp with Window Decoupled: A Fast and Practical Lock-Free Relaxed Queue},
journal={Journal of The Korea Society of Computer and Information},
issn={1598-849X},
year={2025},
volume={30},
number={12},
pages={1-14}
TY - JOUR
AU - Yong-Joon Cho
AU - Nai-Hoon Jung
TI - Time-Stamp with Window Decoupled: A Fast and Practical Lock-Free Relaxed Queue
JO - Journal of The Korea Society of Computer and Information
PY - 2025
VL - 30
IS - 12
PB - The Korean Society Of Computer And Information
SP - 1
EP - 14
SN - 1598-849X
AB - To address the limitations of strict FIFO lock-free queues, relaxed queues have been actively studied as a way to loosen the FIFO constraint and improve parallelism. In this work, we present the Time-Stamped Window Decoupled Queue, a novel relaxed queue that integrates time-stamping with the window-decoupled approach. Experimental results demonstrate that our design outperforms existing relaxed queues in both micro- and macro-benchmarks. Notably, in microbenchmarks, the proposed queue achieves significantly higher performance as the enqueue rate increases, surpassing other relaxed queues.
In a microbenchmark with 72 threads, our queue delivers 60.67% higher throughput than the d-Choice Balanced Operations Queue.
KW - Parallel Processing;Data structure;Lock-free;Queue;Relaxation
DO -
UR -
ER -
Yong-Joon Cho and Nai-Hoon Jung. (2025). Time-Stamp with Window Decoupled: A Fast and Practical Lock-Free Relaxed Queue. Journal of The Korea Society of Computer and Information, 30(12), 1-14.
Yong-Joon Cho and Nai-Hoon Jung. 2025, "Time-Stamp with Window Decoupled: A Fast and Practical Lock-Free Relaxed Queue", Journal of The Korea Society of Computer and Information, vol.30, no.12 pp.1-14.
Yong-Joon Cho, Nai-Hoon Jung "Time-Stamp with Window Decoupled: A Fast and Practical Lock-Free Relaxed Queue" Journal of The Korea Society of Computer and Information 30.12 pp.1-14 (2025) : 1.
Yong-Joon Cho, Nai-Hoon Jung. Time-Stamp with Window Decoupled: A Fast and Practical Lock-Free Relaxed Queue. 2025; 30(12), 1-14.
Yong-Joon Cho and Nai-Hoon Jung. "Time-Stamp with Window Decoupled: A Fast and Practical Lock-Free Relaxed Queue" Journal of The Korea Society of Computer and Information 30, no.12 (2025) : 1-14.
Yong-Joon Cho; Nai-Hoon Jung. Time-Stamp with Window Decoupled: A Fast and Practical Lock-Free Relaxed Queue. Journal of The Korea Society of Computer and Information, 30(12), 1-14.
Yong-Joon Cho; Nai-Hoon Jung. Time-Stamp with Window Decoupled: A Fast and Practical Lock-Free Relaxed Queue. Journal of The Korea Society of Computer and Information. 2025; 30(12) 1-14.
Yong-Joon Cho, Nai-Hoon Jung. Time-Stamp with Window Decoupled: A Fast and Practical Lock-Free Relaxed Queue. 2025; 30(12), 1-14.
Yong-Joon Cho and Nai-Hoon Jung. "Time-Stamp with Window Decoupled: A Fast and Practical Lock-Free Relaxed Queue" Journal of The Korea Society of Computer and Information 30, no.12 (2025) : 1-14.
