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 elimination-backoff stack 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 Journal Article
%1 1664182
%A Hendler, Danny
%A Shavit, Nir
%A Yerushalmi, Lena
%C Orlando, FL, USA
%D 2010
%I Academic Press, Inc.
%J J. Parallel Distrib. Comput.
%K LockFree Me:ToRead
%N 1
%P 1--12
%R 10.1016/j.jpdc.2009.08.011
%T A scalable lock-free stack algorithm
%U http://portal.acm.org/citation.cfm?id=1663671.1664182&coll=Portal&dl=GUIDE&CFID=84819369&CFTOKEN=40932755
%V 70
%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 elimination-backoff stack 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.
@article{1664182,
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 elimination-backoff stack 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.},
added-at = {2010-04-05T13:11:53.000+0200},
address = {Orlando, FL, USA},
author = {Hendler, Danny and Shavit, Nir and Yerushalmi, Lena},
biburl = {https://www.bibsonomy.org/bibtex/2e0e911d9f2bb46eb3464555a8661db25/gron},
description = {A scalable lock-free stack algorithm},
doi = {10.1016/j.jpdc.2009.08.011},
interhash = {fdcd2b330247efb6bc7a2c34021cddab},
intrahash = {e0e911d9f2bb46eb3464555a8661db25},
issn = {0743-7315},
journal = {J. Parallel Distrib. Comput.},
keywords = {LockFree Me:ToRead},
number = 1,
pages = {1--12},
publisher = {Academic Press, Inc.},
timestamp = {2010-04-05T13:11:53.000+0200},
title = {A scalable lock-free stack algorithm},
url = {http://portal.acm.org/citation.cfm?id=1663671.1664182&coll=Portal&dl=GUIDE&CFID=84819369&CFTOKEN=40932755},
volume = 70,
year = 2010
}