Computer Science Speaking Skills Talk

Monday, November 21, 2022 - 12:00pm to 1:00pm

Location:

In Person Traffic21 Classroom, Gates Hillman 6501

Speaker:

YUANHAO WEI, Ph.D. StudentComputer Science DepartmentCarnegie Mellon University

Snapshotting Concurrent Data Structures

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. 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. Presented in Partial Fulfillment of the CSD Speaking Skills Requirement

For More Information, Contact:

Keywords:

Speaking Skills