Robert E. Tarjan
James S. McDonnell Distinguished University Professor of Computer Science
Chief Scientist of Intertrust Technologies.
"Concurrent Disjoint Set Union"
Abstract: The disjoint setunion problem is a classical problem in data structures with a simple and efficient sequential solution that has a notoriously complicated analysis. In certain applications the problem instances can be very large, raising the question of whether concurrency can produce significant speedups. My talk explores this question. I shall describe concurrent versions of standard sequential algorithms that use single and double compare-and-swap primitives for synchronization, making them wait-free. The concurrent algorithms have work bounds that grow logarithmically with the number of processors, suggesting the possibility of significant speedup in practice. These results are part of ongoing joint work with Siddhartha Jayanti, a graduate student at MIT previously at Princeton.
Dr. Tarjan has been a Chaired Professor at Princeton since 1985, having previously held academic positions at Cornell, Berkeley, Stanford and NYU. He has held industrial research positions at Bell Labs, NEC, HP, Microsoft and Intertrust Technologies. He received the Nevanlina Prize in Informatics, given by the International Mathematical Union (IMU), in 1982, and the Association for Computing Machinery (ACM) A.M. Turing Award in 1986. He is a member of the U.S. National Academy of Science (NAS), the U. S. National Academy of Engineering (NAE), a Fellow of the American Philosophical Society (APS) and the American Academy of Arts and Sciences (AAAS). Dr. Tarjan has published more than 250 papers, mostly in the areas of the design and analysis of data structures and graph and network algorithms.
The Department of Computer Science Distinguished Lecture Series is named the “C.C. ‘Kelly’ Gotlieb Distinguished Lecture Series” in honour of the late Professor Emeritus (1921-2016) and first department chair (1964-68) who is widely regarded as the "Father of Computing in Canada". This series promotes distinguished scholarship in the field.