Multi-point Queries on Concurrent Data Structures

Speaker: Yuanhao Wei , Carnegie Mellon University

Date: Wednesday, December 08, 2021

Time: 4:00 PM to 5:00 PM Note: all times are in the Eastern Time Zone

Public: Yes

Location: https://mit.zoom.us/meeting/register/tJMtdOqgrTwsGNV_k0Nk6JjLMk-G6GFzTRyk

Event Type: Seminar

Room Description:

Host: Julian Shun, MIT CSAIL

Contact: Linda Lynch, 715-2459, lindalynch@csail.mit.edu

Relevant URL: http://fast-code.csail.mit.edu/

Speaker URL: None

Speaker Photo:
None

Reminders to: fast-code-seminar@lists.csail.mit.edu, seminars@csail.mit.edu, pl@csail.mit.edu, commit@lists.csail.mit.edu, toc@csail.mit.edu

Reminder Subject: TALK: Multi-point Queries on Concurrent Data Structures

******************IMPORTANT NOTE ABOUT REGISTRATION******************
- The registration link for Fall 2021 is different than from the link from previous terms, so you will need to register again.
- Please save the Zoom link that you receive after you register. This link will stay the same for all subsequent Fast Code seminars.
- Zoom does not recognize a second registration, and will not send out the link a second time. The organizers will not be notified of any second registration.
- If you have any problems with registration, please contact lindalynch@csail.mit.edu by 3:30pm on the day of the seminar, so that we can try to resolve it before the seminar begins.
*********************************************************************

Abstract: Most work on concurrent data structures has focused on supporting single-point operations, such as insert, delete, and lookup, but many applications require supporting these alongside multi-point queries, such as searching for ranges of keys, finding the first key that matches some criteria, or checking if a collection of keys are all present. In this presentation, I'll cover a general technique for adding linearizable multi-point queries to existing concurrent data structures (joint with Naama Ben-David, Guy Blelloch, Panagiota Fatourou, Eric Ruppert, and Yihan Sun). This technique maintains the time bounds and progress properties (e.g. lock-freedom/wait-freedom) of the original data structure. Furthermore, multi-point queries written with this technique are wait-free and take time proportional to their sequential complexity plus a contention term representing the number of update operations concurrent with the query.

Bio: Yuanhao Wei is a PhD at Carnegie Mellon University advised by Guy Blelloch. His primary research interests are in the intersection of theory and practice in distributed computing. His recent work focuses on designing general techniques for theoretically efficient and practical concurrent data structures. Yuanhao is the recipient of an NSERC postgraduate scholarship.

Research Areas:
Algorithms & Theory, Programming Languages & Software

Impact Areas:

This event is not part of a series.

Created by Julian J. Shun at Wednesday, December 01, 2021 at 12:04 PM.