Fast Code Seminar: Size Operation for Concurrent Data Structures

Speaker: Gal Sela , Technion - Israel Institute of Technology

Date: Thursday, May 11, 2023

Time: 1:00 PM to 2:00 PM Note: all times are in the Eastern Time Zone

Public: Yes

Location: 32-G882

Event Type: Seminar

Room Description:

Host: Julian Shun, MIT CSAIL

Contact: Julian Shun, 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: Fast Code Seminar: Size Operation for Concurrent Data Structures

This is hybrid meeting. The physical room is 32-G882. The Zoom registration link is https://mit.zoom.us/meeting/register/tJMtdOqgrTwsGNV_k0Nk6JjLMk-G6GFzTRyk.

******************IMPORTANT NOTE ABOUT ONLINE REGISTRATION******************
- The registration link for 2023 is the same as the link from 2022.
- 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 12pm on the day of the seminar, so that we can try to resolve it before the seminar begins.
*********************************************************************
Abstract:
The size of a data structure (i.e., the number of elements in it) is a widely used property. However, for concurrent programs, obtaining a correct size efficiently is non-trivial, and in fact, there exists no mechanism for that in the literature.
We start by reviewing desired properties for concurrent data structures in general, and continue to the challenges in achieving them when designing a concurrent size operation. We then present the first methodology for adding a concurrent size operation which is both correct (linearizable) and efficient (wait-free and with time complexity independent of data-structure size) to sets and dictionaries. A Java evaluation demonstrates that our size operation executes faster by orders of magnitude compared to existing linearizable solutions.

Bio:
Gal is a PhD student in the Faculty of Computer Science at the Technion - Israel Institute of Technology, advised by professor Erez Petrank. Her research focuses on algorithms for concurrent data structures and distributed computing. Gal received her MSc and BSc in Computer Science from the Technion, both summa cum laude. She was a research intern at VMWare Research Group and a software engineer at Microsoft. Gal is the recipient of several awards, including the Jacobs Fellowship for Outstanding Graduate Students, the Alfred and Anna Grey Excellence Scholarship and Ernest Freudman Special Excellence Fellowship.

Research Areas:
Algorithms & Theory, Programming Languages & Software

Impact Areas:

This event is not part of a series.

Created by Julian J. Shun at Tuesday, April 11, 2023 at 11:16 AM.