Poster 58: Lock-Free van Emde Boas Array
TimeThursday, 21 November 20198:30am - 5pm
DescriptionLock-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.