2010 · 190 citations · 21 references
ComputingComputer EngineeringComputer ScienceFault ToleranceFault-tolerant ComputingFault-tolerant SystemsShared-memory MultiprocessingShared-memory ParallelismAsynchronous MemoryBinary SearchBinary Search TreesCompare-and-swapShared Memory ConcurrencyShared Memory ManagementShared-memory Data StructuresSwap Operations
This paper describes the first complete implementation of a non-blocking binary search tree in an asynchronous shared-memory system using single-word compare-and-swap operations. The implementation is linearizable and tolerates any number of crash failures. Insert and Delete operations that modify different parts of the tree do not interfere with one another, so they can run completely concurrently. Find operations only perform reads of shared memory.
21
Maurice Herlihy · ACM Transactions on Programming Languages and Systems · 1991 · 1.8K citations · Full text
Software transactional memory for dynamic-sized data structures
Maurice Herlihy, Victor Luchangco, Mark Moir et al. · 2003 · 999 citations
A dichromatic framework for balanced trees
Leo J. Guibas, Robert Sedgewick · 1978 · 658 citations