TY - GEN
T1 - Keynote Talk
T2 - 45th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, PODC 2026
AU - Tarjan, Robert E.
N1 - Publisher Copyright:
© 2026 Copyright held by the owner/author(s).
PY - 2026/7/1
Y1 - 2026/7/1
N2 - This talk will explore whether and by how much operations on data structures can be sped up by using multiple highly unsynchronized threads. Taking advantage of concurrency in this setting is a challenge. The talk will describe work by Siddhartha Jayanti and the speaker on the efficiency of concurrent disjoint set union algorithms, including recent unpublished work that uses new ideas to eliminate the need for randomization. It will also discuss ongoing work with Laxman Dhulipala, Jakub Łȩcki, and Siddhartha Jayanti on finding maximal matchings, as well as the general question of what we should require in a realistic but theoretically tractable model of highly asynchronous concurrency.
AB - This talk will explore whether and by how much operations on data structures can be sped up by using multiple highly unsynchronized threads. Taking advantage of concurrency in this setting is a challenge. The talk will describe work by Siddhartha Jayanti and the speaker on the efficiency of concurrent disjoint set union algorithms, including recent unpublished work that uses new ideas to eliminate the need for randomization. It will also discuss ongoing work with Laxman Dhulipala, Jakub Łȩcki, and Siddhartha Jayanti on finding maximal matchings, as well as the general question of what we should require in a realistic but theoretically tractable model of highly asynchronous concurrency.
KW - asynchronous algorithms
KW - concurrent data structures
KW - disjoint set union
KW - maximal matching
KW - theory of distributed computing
UR - https://www.scopus.com/pages/publications/105044279956
UR - https://www.scopus.com/pages/publications/105044279956#tab=citedBy
U2 - 10.1145/3796701.3820746
DO - 10.1145/3796701.3820746
M3 - Conference contribution
AN - SCOPUS:105044279956
T3 - Proceedings of the Annual ACM Symposium on Principles of Distributed Computing
SP - 4
BT - PODC 2026 - Proceedings of the 2026 ACM Symposium on Principles of Distributed Computing
PB - Association for Computing Machinery
Y2 - 6 July 2026 through 10 July 2026
ER -