Best Paper Presentation Award at intl. workshop LCPC 2011
© 2011 EPFL
The paper "Lock-Free Resizeable Concurrent Tries" published at the 24th International Workshop on Languages and Compilers for Parallel Computing (LCPC 2011) in Fort Collins, Colorado, won the Best Paper Presentation Award in a tie for the first place.
The LCPC workshop is a forum for sharing research on all aspects of parallel languages, compilers and related topics including runtime systems and tools. It is sponsored by Intel, Google and the NSF. The scope of the workshop spans foundational results and practical experience. All accepted papers are published by Springer.
One of the main challenges of programming parallel computers is adapting existing sequential primitives to a parallel setting. Data structures are one of the most widely spread programming abstractions that need to be parallelized. Concurrent lock-free data structures are among the most efficient ways to do this.
The paper describes a new implementation of a lock-free concurrent data structure, along with a correctness proof and experimental evaluation. It is shown that insert and remove operations are particularly scalable for this data structure, making it useful for various kinds of parallel programs.
The full abstract and the extended version of this paper are also available as a technical report - http://infoscience.epfl.ch/record/166908.