The literature describes two high performance concurrent stack algorithms based on combining funnels and elimination trees. Unfortunately, the funnels are linearizable but blocking, and the elimination trees are non-blocking but not linearizable. Neither is used in practice since they perform well only at exceptionally high loads. The literature also describes a simple lock-free linearizable stack algorithm that works at low loads but does not scale as the load increases. The question of designing a stack algorithm that is non-blocking, linearizable, and scales well throughout the concurrency range, has thus remained open.This paper presents such a concurrent stack algorithm. It is based on the following simple observation: that a single elimination array used as a backoff scheme for a simple lock-free stack is lock-free, linearizable, and scalable. As our empirical results show, the resulting <i>elimination-backoff stack</i> performs as well as the simple stack at low loads, and increasingly outperforms all other methods (lock-based and non-blocking) as concurrency increases. We believe its simplicity and scalability make it a viable practical alternative to existing constructions for implementing concurrent stacks.
%0 Conference Paper
%1 Hendler:2004:SLS
%A Hendler, Danny
%A Shavit, Nir
%A Yerushalmi, Lena
%B Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures
%D 2004
%I ACM
%K Array Collections Concurrent Elimination LockFree Scalable Stack
%P 206--215
%R 10.1145/1007912.1007944
%T A Scalable Lock-free Stack Algorithm
%X The literature describes two high performance concurrent stack algorithms based on combining funnels and elimination trees. Unfortunately, the funnels are linearizable but blocking, and the elimination trees are non-blocking but not linearizable. Neither is used in practice since they perform well only at exceptionally high loads. The literature also describes a simple lock-free linearizable stack algorithm that works at low loads but does not scale as the load increases. The question of designing a stack algorithm that is non-blocking, linearizable, and scales well throughout the concurrency range, has thus remained open.This paper presents such a concurrent stack algorithm. It is based on the following simple observation: that a single elimination array used as a backoff scheme for a simple lock-free stack is lock-free, linearizable, and scalable. As our empirical results show, the resulting <i>elimination-backoff stack</i> performs as well as the simple stack at low loads, and increasingly outperforms all other methods (lock-based and non-blocking) as concurrency increases. We believe its simplicity and scalability make it a viable practical alternative to existing constructions for implementing concurrent stacks.
%@ 1-58113-840-7
@inproceedings{Hendler:2004:SLS,
abstract = {The literature describes two high performance concurrent stack algorithms based on combining funnels and elimination trees. Unfortunately, the funnels are linearizable but blocking, and the elimination trees are non-blocking but not linearizable. Neither is used in practice since they perform well only at exceptionally high loads. The literature also describes a simple lock-free linearizable stack algorithm that works at low loads but does not scale as the load increases. The question of designing a stack algorithm that is non-blocking, linearizable, and scales well throughout the concurrency range, has thus remained open.This paper presents such a concurrent stack algorithm. It is based on the following simple observation: that a single elimination array used as a backoff scheme for a simple lock-free stack is lock-free, linearizable, and scalable. As our empirical results show, the resulting <i>elimination-backoff stack</i> performs as well as the simple stack at low loads, and increasingly outperforms all other methods (lock-based and non-blocking) as concurrency increases. We believe its simplicity and scalability make it a viable practical alternative to existing constructions for implementing concurrent stacks.},
acmid = {1007944},
added-at = {2012-08-27T00:09:58.000+0200},
author = {Hendler, Danny and Shavit, Nir and Yerushalmi, Lena},
biburl = {https://www.bibsonomy.org/bibtex/264859aef95fbd1288ce6e95f90a79560/gron},
booktitle = {Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures},
description = {A scalable lock-free stack algorithm},
doi = {10.1145/1007912.1007944},
interhash = {fee7747d8ecc64db6174a989da93a9b6},
intrahash = {64859aef95fbd1288ce6e95f90a79560},
isbn = {1-58113-840-7},
keywords = {Array Collections Concurrent Elimination LockFree Scalable Stack},
location = {Barcelona, Spain},
numpages = {10},
pages = {206--215},
publisher = {ACM},
series = {SPAA'04},
timestamp = {2018-03-06T10:49:30.000+0100},
title = {{A Scalable Lock-free Stack Algorithm}},
year = 2004
}