Dartmouth Events

Full events calendar

Simple, Fast, Scalable, and Reliable Distributed Algorithms

Siddhartha Jayanti a research scientist at Google Research, Cambridge, presents his research on the classic concurrent set union data structure.

Monday, May 13, 2024
11:30am – 12:00pm
ECSC 009
Intended Audience(s): Public
Categories: Arts and Sciences
In this talk, I will focus on my research into the classic concurrent set union data structure. I present the first scalable algorithm for concurrent union-find, which is designed for the highly adversarial asynchronous shared-memory model, while simultaneously achieving near-linear speed-ups over the classic sequential solution in parallel computation models. Our lower bounds show that the time complexities of our algorithms are near-optimal. I also furnish the algorithm with a machine-verified proof of correctness. 
 
Our algorithms are fast in practice and have seen wide adoption. They are implemented in Google's recently open-sourced graph-mining library, where they enable “parallel clustering algorithms which scale to graphs with tens of billions of edges”. An MIT research group independently implemented hundreds of parallel algorithms for connected components and revealed that our algorithms are consistently the fastest both on CPUs and GPUs. 
 
I will also briefly mention some of my contributions to other areas of research, including machine learning, economics, security, and verification.
For more information, contact:
Julia Ganson
Julia.D.Ganson@dartmouth.edu
Permanent URL to this event: https://web.cs.dartmouth.edu/events/event?event=74316

Events are free and open to the public unless otherwise noted.