Talk Title: Open problems in asynchronous wait-free computing

Abstract: The talk will describe two or three open problems that I find intriguing. We'll discuss why we care about these problems, and what is known about them so far.

Speaker Bio: Hagit Attiya is a professor at the department of Computer Science at the Technion, Israel Institute of Technology, and holds the Harry W. Labov and Charlotte Ullman Labov Academic Chair. She is the editor-in-chief of Springer's journal Distributed Computing. She received the Dijkstra award in Distributed Computing 2011 and is a fellow of the ACM.

Talk Title: Simple, Fast, Scalable, and Reliable Multiprocessor Algorithms: A Journey through Concurrent Set Union

Abstract: In this age of the multicore revolution, efficient multiprocessor algorithms are the need of the hour. In this talk, I identify simplicity, speed, scalability, and reliability as four core algorithmic design goals for multicore algorithms, and present our concurrent algorithms for the union-find data structure that meet these goals. Specifically, I present the first scalable algorithm for concurrent union-find, which has a work complexity of only Θ(α(n, m/(np)) + log(np/m + 1)), thereby providing almost-linear speed-up. I show that this work-complexity is optimal amongst a class of symmetric algorithms, which captures the complexities of all known concurrent union-find algorithms. I also furnish the algorithm with a machine-verified proof of correctness. The algorithm is lightning quick in practice: an MIT research group independently implemented hundreds of parallel algorithms for connected components and revealed that the algorithms in this thesis are consistently the fastest on both CPUs and GPUs. As an illustration, the algorithms were used to compute the components of the Hyperlink2012 graph of 128 billion edges in just 8.2 seconds on a standard 72 core machine, which is 3.1x faster than the state-of-the-art in any computational setting. Our algorithms have also improved the state-of-the-art in clustering, and in computing strongly connected components for model checking.

This talk is based on my Ph.D. dissertation on Simple, Fast, Scalable, and Reliable Multiprocessor Algorithms.

Speaker Bio: Siddhartha Jayanti is a Research Scientist at Google Research, where his research spans distributed computing, algorithms, machine learning, security, economics and computing, and formal verification. He received his Ph.D. in Computer Science from MIT with a minor in Machine Learning in 2023. He also holds an S.M. in EECS from MIT and a B.S.E. in Computer Science with a certificate in Applied and Computational Mathematics from Princeton University.

Siddhartha's Ph.D. dissertation was awarded the ACM-EATCS Principles of Distributed Computing Doctoral Dissertation Award. Siddhartha's Ph.D. research was funded by a National Defense Science and Engineering Graduate (NDSEG) Fellowship. Siddhartha was also awarded the NSF Graduate Research Fellowship, the Barry Goldwater Scholarship, and the Channels Scholarship from NSF's Center for Science of Information. He also received the Outstanding Computer Science Senior Thesis Prize from the Princeton computer science department, the Calvin Dodd Maccracken Senior Thesis Award from Princeton's school of engineering and applied sciences, and was Runner-Up for CRA's Outstanding Undergraduate Research Award.

Talk Title: The New Era of Persistent Data Structures

Abstract: With the recent launch of the Intel Optane memory platform, non-volatile main memory in the form of fast, dense, byte-addressable, and persistent memory has become available. Nevertheless, designing crash-resilient algorithms and data structures is complex and error-prone, especially when caches and machine registers are still volatile and the data residing in memory after a crash might not reflect a consistent view of the program state. 

Even though Intel deprecated its product, Compute Express Link (CXL)'s non-volatile attachment point is a potential path forward. Moreover, by using CXL memory pooling, multiple hosts can share the same memory, including from remote devices. Therefore, the inconsistencies challenges of non-volatile memory remain relevant, even when memory is volatile.

This talk will present different approaches and transformations for adding durability to lock-free data structures, with a low performance overhead, while leveraging and dealing with all the complexities of non-volatile main memory. Moreover, it will describe the most recent advances in CXL and the opportunities that arise from using this technology in the context of persistent programs.

Speaker Bio: Michal Friedman is a postdoctoral researcher at the Systems Group of ETH, working with Prof. Gustavo Alonso. Her research interests are broad and include systems, concurrent computing, and programming languages. She focuses on understanding the factors affecting different hardware components and developing optimized solutions that take these factors into account. In particular, she is interested in designing general solutions for running concurrent programs on emerging hardware platforms. She obtained a Ph.D. in Computer Science at the Technion, advised by Prof. Erez Petrank, and was generously supported by the Azrieli Foundation Fellowship. In her Ph.D. thesis, she focused on developing concurrent data structures for non-volatile memories.

Talk Title: Trust is Priceless, Distrust is Costly: The Price of Coordination in the Theater of Traitors

Abstract: In the vast realm of asynchronous distributed computing, Byzantine faults stand as a challenge, captivating researchers for over 40 years. As we navigate through pivotal asynchronous distributed tasks, we will continually spotlight the efforts made to mitigate the costs while ensuring fault tolerance. Drawing upon the latest research, we will explore the trade-offs, the balance, and the inherent costs associated with managing Byzantine behaviors. While the talk will provide a comprehensive overview of current findings, it also aims to underscore the ongoing quest to optimize and reduce the complexity of such distrustful collaboration.

While the rewards of Byzantine coordination are great, they are certainly not free!

Speaker Bio: Pierre Civit is a postdoctoral researcher at EPFL. He received the M.S. in Aerospace Engineering from the ISAE-Supaéro in 2019, and a Ph.D. in Computer Science from the Sorbonne University, France, in 2022. He has been visiting scholar at Georgia Tech and at the University of Sydney. His current research interests include secure distributed computing, and automata theory.

Talk Title: Distribu-Red meets Blockchain: the scalability and usability story

Abstract: The talk will focus on the areas and research directions that I have had experience with at Novi and Aptos Labs. It will touch upon the quest for scalable Byzantine Fault Tolerant consensus, then dive deeper into transaction execution. In particular, how research in Software Transactional Memory inspired the design of the BlockSTM parallel execution system (state of the art when no prior read-write hints are provided). We will overview the observed limitations of prior research, as well as Block-STM, and further ways, such as transaction reordering, and Aggregators, to avoid R/W conflicts and sequential dependencies. Aggregators, which can be viewed as a first semblance of a concurrency primitive in a smart contract programming language model, are a good case study for matching research with industrial motivation and crucially, needs that dictate the full specification.

Speaker Bio: Rati Gelashvili obtained his PhD in 2017 from MIT with research centered around the complexity of synchronization. He has received the PODC best dissertation award and best paper awards at DISC 2015 and DISC 2021. Rati did a postdoctoral fellowship w. Prof. Faith Ellen at the University of Toronto, after which he was an engineering team lead at NeuralMagic and a research scientist at Novi. Rati is currently Blockchain researcher and member of the founding team at Aptos Labs.