Data Structures of the Future: Concurrent, Optimistic, and Relaxed
Speaker: Dan Alistarh – Klosterneuburg, AustriaTopic(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: 30Duration: 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.