Abstract
This paper introduces new lock-free and wait-free unordered linked list algorithms. The composition of these algorithms according to the fast-path-slow-path methodology, a recently devised approach to creating fast wait-free data structures, is nontrivial, suggesting limitations to the applicability of the fast-path-slow-path methodology. The list algorithms introduced in this paper are shown to scale well across a variety of benchmarks, making them suitable for use both as standalone lists, and as the foundation for wait-free stacks and non-resizable hash tables.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Attiya, H., Hillel, E.: Built-In Coloring for Highly-Concurrent Doubly-Linked Lists. In: Dolev, S. (ed.) DISC 2006. LNCS, vol. 4167, pp. 31–45. Springer, Heidelberg (2006)
Braginsky, A., Petrank, E.: Locality-Conscious Lock-Free Linked Lists. In: Proceedings of the 12th International Conference on Distributed Computing and Networking, Bangalore, India (January 2011)
Colvin, R., Groves, L., Luchangco, V., Moir, M.: Formal verification of a lazy concurrent list-based set algorithm. In: Ball, T., Jones, R.B. (eds.) CAV 2006. LNCS, vol. 4144, pp. 475–488. Springer, Heidelberg (2006)
Ellen, F., Fatourou, P., Kosmas, E., Milani, A., Travers, C.: Universal Constructions that Ensure Disjoint-Access Parallelism and Wait-Freedom. In: Proceedings of the 2012 ACM Symposium on Principles of Distributed Computing (July 2012)
Ellen, F., Fatourou, P., Ruppert, E., van Breugel, F.: Non-blocking Binary Search Trees. In: Proceedings of the 29th ACM Symposium on Principles of Distributed Computing, Zurich, Switzerland (July 2010)
Fatourou, P., Kallimanis, N.D.: A Highly-Efficient Wait-Free Universal Construction. In: Proceedings of the 23rd ACM Symposium on Parallelism in Algorithms and Architectures, San Jose, CA (June 2011)
Fomitchev, M., Ruppert, E.: Lock-Free Linked Lists and Skip Lists. In: Proceedings of the 23rd ACM Symposium on Principles of Distributed Computing, St. John’s, Newfoundland, Canada (July 2004)
Harris, T.L.: A Pragmatic Implementation of Non-Blocking Linked Lists. In: Welch, J.L. (ed.) DISC 2001. LNCS, vol. 2180, pp. 300–314. Springer, Heidelberg (2001)
Heller, S., Herlihy, M.P., Luchangco, V., Moir, M., Scherer III, W.N., Shavit, N.N.: A Lazy Concurrent List-Based Set Algorithm. In: Anderson, J.H., Prencipe, G., Wattenhofer, R. (eds.) OPODIS 2005. LNCS, vol. 3974, pp. 3–16. Springer, Heidelberg (2006)
Herlihy, M.: Wait-Free Synchronization. ACM Transactions on Programming Languages and Systems 13(1), 124–149 (1991)
Herlihy, M.: A Methodology for Implementing Highly Concurrent Data Objects. ACM Transactions on Programming Languages and Systems 15(5), 745–770 (1993)
Herlihy, M., Shavit, N.: The Art of Multiprocessor Programming. Morgan Kaufmann (2008)
Herlihy, M.P., Wing, J.M.: Linearizability: A Correctness Condition for Concurrent Objects. ACM Transactions on Programming Languages and Systems 12(3), 463–492 (1990)
Kogan, A., Petrank, E.: Wait-Free Queues with Multiple Enqueuers and Dequeuers. In: Proceedings of the 16th ACM Symposium on Principles and Practice of Parallel Programming, San Antonio, TX (February 2011)
Kogan, A., Petrank, E.: A Methodology for Creating Fast Wait-Free Data Structures. In: Proceedings of the 16th ACM Symposium on Principles and Practice of Parallel Programming, New Orleans, LA (February 2012)
Michael, M.: High Performance Dynamic Lock-Free Hash Tables and List-Based Sets. In: Proceedings of the 14th ACM Symposium on Parallel Algorithms and Architectures, Winnipeg, Manitoba, Canada (August 2002)
Michael, M.: Hazard Pointers: Safe Memory Reclamation for Lock-Free Objects. IEEE Transactions on Parallel and Distributed Systems 15(6), 491–504 (2004)
Michael, M.M., Scott, M.L.: Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms. In: Proceedings of the 15th ACM Symposium on Principles of Distributed Computing (May 1996)
O’Hearn, P.W., Rinetzky, N., Vechev, M.T., Yahav, E., Yorsh, G.: Verifying Linearizability with Hindsight. In: Proceedings of the 29th ACM Symposium on Principles of Distributed Computing, Zurich, Switzerland (July 2010)
Prokopec, A., Bronson, N., Bagwell, P., Odersky, M.: Concurrent Tries with Efficient Non-Blocking Snapshots. In: Proceedings of the 17th ACM Symposium on Principles and Practice of Parallel Programming (February 2012)
Sundell, H., Tsigas, P.: Fast and Lock-Free Concurrent Priority Queues for Multi-Thread Systems. Journal of Parallel and Distributed Computing 65, 609–627 (2005)
Sundell, H., Tsigas, P.: Lock-Free Deques and Doubly Linked Lists. Journal of Parallel and Distributed Computing 68(7) (July 2008)
Timnat, S., Braginsky, A., Kogan, A., Petrank, E.: Wait-Free Linked-Lists. In: Baldoni, R., Flocchini, P., Binoy, R. (eds.) OPODIS 2012. LNCS, vol. 7702, pp. 330–344. Springer, Heidelberg (2012)
Valois, J.: Lock-free linked lists using compare-and-swap. In: Proceedings of the Fourteenth Annual ACM Symposium on Principles of Distributed Computing, Ottowa, Ontario, Canada (August 1995)
Zhang, K., Zhao, Y., Yang, Y., Liu, Y., Spear, M.: Practical Non-blocking Unordered Lists. Technical Report LU-CSE-13-003, Lehigh University (2013)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Zhang, K., Zhao, Y., Yang, Y., Liu, Y., Spear, M. (2013). Practical Non-blocking Unordered Lists. In: Afek, Y. (eds) Distributed Computing. DISC 2013. Lecture Notes in Computer Science, vol 8205. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-41527-2_17
Download citation
DOI: https://doi.org/10.1007/978-3-642-41527-2_17
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-41526-5
Online ISBN: 978-3-642-41527-2
eBook Packages: Computer ScienceComputer Science (R0)