Document Type
Technical Report
Publication Date
1-2011
Subjects
Synchronization, Data structures (Computer science), Computer networks -- Scalability, Computer multitasking
Abstract
Operating system performance and scalability on sharedmemory many-core systems depends critically on efficient access to shared data structures. Scalability has proven difficult to achieve for many data structures. In this paper we present a novel and highly scalable concurrent red-black tree. Red-black trees are widely used in operating systems, but typically exhibit poor scalability. Our red-black tree has linear read scalability, uncontended read performance that is at least 25% faster than other known approaches, and deterministic lookup times for a given tree size, making it suitable for realtime applications.
Persistent Identifier
http://archives.pdx.edu/ds/psu/10384
Citation Details
Howard, Philip W., and Jonathan Walpole. Relativistic red-black trees. Technical Report 10-06, Portland State University, Computer Science Department, 2010.
Description
Portland State University Computer Science Department Technical Report 10-06, January 2011.