Poster 58: Lock-Free van Emde Boas Array

Authors: Ziyuan Guo (University of Tokyo)

Abstract: Lock-based data structures have some potential issues such as deadlock, livelock, and priority inversion, and the progress can be delayed indefinitely if the thread that is holding locks cannot acquire a timeslice from the scheduler. Lock-free data structures, which guarantees the progress of some method call, can be used to avoid these problems. This poster introduces the first lock-free concurrent van Emde Boas Array which is a variant of van Emde Boas Tree. It is linearizable, and the benchmark shows significant performance improvement comparing to other lock-free search trees when the date set is large and dense enough.

Best Poster Finalist (BP): no

Poster: PDF
Poster summary: PDF


Back to Poster Archive Listing