Write a Blog >>
Mon 24 Feb 2020 14:25 - 14:50 - Concurrent Data Structures (Mediterranean Ballroom) Chair(s): Michael Scott

Concurrency has been a subject of study for more than 50 years. Still, many developers struggle to adapt their sequential code to be accessed concurrently. This need has pushed for generic solutions and specific concurrent data structures.

Wait-free universal constructs are attractive as they can turn a sequential implementation of any object into an equivalent, yet concurrent and wait-free, implementation. While highly relevant from a research perspective, these techniques are of limited practical use when the underlying object or data structure is sizable. The copy operation can consume much of the CPU’s resources and significantly degrade performance.

To overcome this limitation, we have designed CX, a multi-instance-based wait-free universal construct that substantially reduces the amount of copy operations. The construct maintains a bounded number of instances of the object that can potentially be brought up to date. We applied CX to several sequential implementations of data structures, including STL implementations, and compared them with existing wait-free constructs. Our evaluation shows that CX performs significantly better in most experiments, and can even rival with hand-written lock-free and wait-free data structures, simultaneously providing wait-free progress, safe memory reclamation and high reader scalability.

Mon 24 Feb

Displayed time zone: Tijuana, Baja California change

14:00 - 15:40
Concurrent Data Structures (Mediterranean Ballroom)Main Conference
Chair(s): Michael Scott
14:00
25m
Talk
Scaling Concurrent Queues by Using HTM to Profit from Failed Atomic Operations
Main Conference
Or Ostrovsky Tel Aviv University, Adam Morrison Tel Aviv University
14:25
25m
Talk
A Wait-Free Universal Construct for Large Objects
Main Conference
Andreia Correia University of Neuchâtel, Pedro Ramalhete , Pascal Felber Université de Neuchâtel
14:50
25m
Talk
Fast Concurrent Data Sketches
Main Conference
Arik Rinberg Technion, Alexander Spiegelman VMware Research, Edward Bortnikov Yahoo Research, Eshcar Hillel Yahoo Research, Oath, Idit Keidar Technion - Israel institute of technology, Hadar Serviansky Weizmann, Lee Rhodes Verizon Media
15:15
25m
Talk
Universal Wait-Free Memory Reclamation
Main Conference
Ruslan Nikolaev Virginia Tech, Binoy Ravindran Virginia Tech