A Lazy Concurrent List-Based Set Algorithm
Abstract
We present a novel “lazy” list-based implementation of a concurrent set object. It is based on an optimistic locking scheme for inserts and removes and includes a simple wait-free membership test. Our algorithm improves on the performance of all previous such algorithms.
A preliminary version of this paper was presented at the 9th International Conference on Principles of Distributed Systems [1].
References
Steve Heller , A lazy concurrent list-based set algorithm, Proceedings of the, 9th International Conference on Principles of Distributed Systems (OPODIS)3974,LNCS (2005) pp. 3–16. Google Scholar-
M. Moir and N. Shavit , Chapter 47 - Concurrent Data Structures - Handbook of Data Structures and Applications ( Chapman and Hall/CRC , 2004 ) . Google Scholar - Acta Inforrnatica 9, 1 (1977). ISI, Google Scholar
J. Valois , Lock-free linked lists using compare-and-swap, ACM Symposium on Principles of Distributed Computing (1995) pp. 214–222. Google Scholar- Lecture Notes in Computer Science 2180, 300 (2001), DOI: 10.1007/3-540-45414-4_21. Crossref, Google Scholar
M. Michael , High performance dynamic lock-free hash tables and list-based sets, Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures (ACM Press, 2002) pp. 73–82. Google Scholar-
Corinne Maier , Hello Laziness: Why Hard Work Doesn't Pay ( Orion, London , 2005 ) . Google Scholar - ACM Transactions on Programming Languages and Systems 13(1), 124 (1991), DOI: 10.1145/114005.102808. Crossref, ISI, Google Scholar
Robert Colvin , Formal verification of a lazy concurrent list-based set algorithm, Proceedings of the 18th International Conference on Computer Aided Verification4144,LNCS (2006) pp. 475–488. Google Scholar- ACM Transactions on Programming Languages and Systems 12(3), 463 (1990), DOI: 10.1145/78969.78972. Crossref, ISI, Google Scholar
M. Herlihy , V. Luchangco and M. Moir , The repeat offender problem: A mechanism for supporting lock-free dynamic-sized data structures, Proceedings of the 16th International Symposium on Distributed Computing2508 (Springer-Verlag, Heidelberg, 2002) pp. 339–353. Google ScholarM. Michael , Safe memory reclamation for dynamic lock-free objects using atomic reads and writes, The 21st Annual ACM Symposium on Principles of Distributed Computing (ACM Press, 2002) pp. 21–30. Google Scholar-
D. Lea , Concurrent Programming in Java(TM): Design Principles and Patterns , 2nd edn. ( Addison-Wesley , 1999 ) . Google Scholar - D. Lea. Personal communication . Google Scholar
M. Herlihy , A simple optimistic skiplist algorithm, Proceedings of the Colloquia on Structural Information and Communication Complexity (SIROCCO 2007) (2007) pp. 124–138. Google Scholar


