Data Structures of the Future: Concurrent, Optimistic, and Relaxed

Speaker:  Dan Alistarh – Klosterneuburg, Austria
Topic(s):  Computational Theory, Algorithms and Mathematics

Abstract

This talk is about a relatively new family of "relaxed" ordered data structures, in the vein of stacks, queues, and priority queues, but which provide weaker semantics than their classical "exact"
counterparts. I will demonstrate the usefulness of such data structures in real applications by introducing a general framework for using relaxed structures to execute a wide class of graph algorithms in a concurrent setting, with provable correctness and performance guarantees. Further, we will present existing scalable data structures implementations which satisfy these semantics. These structures exhibit much higher throughput than standard exact queues in concurrent implementations,while providing provably bounded relaxation semantics.

About this Lecture

Number of Slides:  30
Duration:  45 minutes
Languages Available:  English
Last Updated: 

Request this Lecture

To request this particular lecture, please complete this online form.

Request a Tour

To request a tour with this speaker, please complete this online form.

All requests will be sent to ACM headquarters for review.