paper

A Methodology for Implementing Highly Concurrent Data Structures

  • Authors:
Read the paper

📜 Abstract

We present a methodology for constructing concurrent objects. It captures the notion of high concurrency, allows simple correctness proofs, and yields efficient, portable implementations. A concurrent object is one designed to be shared by concurrent processes. An implementation of a concurrent object is lock-free if it guarantees that infinitely often some process will complete an operation. A major contribution of our methodology is the systematic use of atomic primitive operations to "glue together" short "critical sections" in which shared data is modified.

✨ Summary

This paper by Maurice P. Herlihy and J. Eliot B. Moss introduces a novel methodology for constructing concurrent data structures, commonly known in computer science as non-blocking or lock-free data structures. The methodology emphasizes high concurrency levels while ensuring consistent and efficient operations. Key contributions include the use of atomic primitive operations to connect brief critical sections for modifying shared data. This approach leads to the creation of lock-free concurrent objects, which are vital for modern multithreading environments and shared-memory systems.

The paper’s substantial influence can be traced through its foundational impact on subsequent research in highly concurrent data structures. It is frequently cited alongside Reynold’s lock-free data structure concepts and has become a cornerstone in academic and industrial advancements regarding non-blocking algorithms. Herlihy’s linearizability concept from this work is now a standard correctness condition for concurrent operations.

Citations and References: 1. Fraser, K. (2004). Practical Lock-Free Programming. University of Cambridge Computer Laboratory. 2. Michael, M. M. (2004). Hazard Pointers: Safe Memory Reclamation for Lock-Free Objects. IEEE Transactions on Parallel and Distributed Systems. 3. Shavit, N., & Touitou, D. (1995). Software transactional memory. Distributed Computing, Springer. 4. Boehm, H.-J. (2013). Can seqlocks get along with programming language memory models?. ACM SIGPLAN Notices. 5. Harris, T. L., et al. (2008). Transactional Memory: An Overview. Retrieved from SpringerLink.