Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:Concurrent Disjoint Set Union
Speaker:Prof. Robert E. Tarjan
coming from:Princeton University
Speakers Bio:
Event Type:Talk
Visibility:D1, D2, D3, D4, D5, SWS, RG1, MMCI
We use this to send out email in the morning.
Level:MPI Audience
Date, Time and Location
Date:Friday, 16 September 2016
Duration:45 Minutes
Building:E1 3 - Hörsaal Gebäude
The disjoint set union problem is a classical problem in data structures with a
simple and efficient sequential solution that has a notoriously complicated
analysis. One application is to find strongly connected components in huge,
implicitly defined graphs arising in model checking. In this application, the
use of multiprocessors has the potential to produce significant speedups. We
explore this possibility. We devise and analyze wait-free concurrent
implementations of standard sequential algorithms using single and double
compare-and-swap primitives for synchronization. We obtain work bounds that grow
logarithmically with the number of processors, suggesting the possibility of
significant speedup in practice. This is joint work with Siddhartha Jayanti, an
undergraduate at Princeton.

Robert E. Tarjan is the James S. McDonnell Distinguished University Professor of
Computer Science at Princeton University and the Chief Scientist of Intertrust
Technologies. He has held academic positions at NYU, Stanford, U.C. Berkeley,
and Cornell, and industrial research positions at Microsoft, HP, NEC, and Bell
Labs. He is a world expert in the design and analysis of data structures and
graph and network algorithms. He is a member of the U.S. National Academy of
Sciences, the U.S. National Academy of Engineering . the American Philosophical
Society, and the American Academy of Arts and Sciences. He was awarded the
A.C.M Turing Award in 1986 and the Nevanlinna Prize of the International
Congress of Mathematicians in 1982.
Name(s):Christina Fries
EMail:--email address not disclosed on the web
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):
Christina Fries/AG1/MPII/DE, 09/15/2016 03:38 PM
Last modified:
Uwe Brahm/MPII/DE, 09/16/2016 07:01 AM
  • Christina Fries, 09/15/2016 03:41 PM -- Created document.