Computer Science Speaking Skills Talk

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


In Person Traffic21 Classroom, Gates Hillman 6501


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:


Speaking Skills