World Scientific
  • Search
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×
Our website is made possible by displaying certain online content using javascript.
In order to view the full content, please disable your ad blocker or whitelist our website www.worldscientific.com.

System Upgrade on Tue, Oct 25th, 2022 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.

A Lazy Concurrent List-Based Set Algorithm

    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 Helleret al., 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
    • R. Bayer and M. Schkolnick, Acta Inforrnatica 9, 1 (1977). ISIGoogle Scholar
    • J. Valois, Lock-free linked lists using compare-and-swap, ACM Symposium on Principles of Distributed Computing (1995) pp. 214–222. Google Scholar
    • T. Harris, Lecture Notes in Computer Science 2180, 300 (2001), DOI: 10.1007/3-540-45414-4_21. CrossrefGoogle 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
    • M. Herlihy, ACM Transactions on Programming Languages and Systems 13(1), 124 (1991), DOI: 10.1145/114005.102808. Crossref, ISIGoogle Scholar
    • Robert Colvinet al., 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
    • M. Herlihy and J. Wing, ACM Transactions on Programming Languages and Systems 12(3), 463 (1990), DOI: 10.1145/78969.78972. Crossref, ISIGoogle 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 Scholar
    • M. 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. Herlihyet al., A simple optimistic skiplist algorithm, Proceedings of the Colloquia on Structural Information and Communication Complexity (SIROCCO 2007) (2007) pp. 124–138. Google Scholar