The winners of the 2022 Principles of Distributed Computing Doctoral Dissertation Award are
Dr. Naama Ben-David
for her dissertation
Theoretical Foundations for Practical Concurrent and Distributed Computation
and
Dr. Manuela Fischer
for her dissertation
Local Algorithms for Classic Graph Problems.
Dr. Naama Ben-David completed her thesis on July 22nd, 2020, under the supervision of Prof. Guy E. Blelloch, at Carnegie Mellon University. In her thesis, Dr. Ben-David addressed three modern technologies that play a significant role in concurrent/distributed computing and carefully developed faithful, clean, and theoretically elegant models for each. Based on these models and theories she then developed for each a new distributed algorithm, showed the algorithms applicability in practice, and finally developed practical tools to enable practitioners and theoretical researchers to analyze these systems, and the benefits of the new models and algorithms. The three technologies which Dr. Ben-David addressed in her thesis are: (1) remote direct memory access (RDMA) as a means to share memory among message-passing communicating processors whether in a large network or in a data center, (2) non-volatile random access memories (NVRAM) for which she developed a general simulation that can adapt many classic concurrent algorithms to a setting in which processes using NVRAM can recover after a system fault, and (3) shared-memory concurrent access where Dr. Ben-David developed new careful analysis reflecting their performance in practice.
Dr. Manuela Fischer completed her thesis on 14th June, 2021, under the supervision of Prof. Mohsen Ghaffari, at ETH Zurich. Dr. Fischer’s thesis contains a large consistent set of outstanding achievements in the design of distributed algorithms for numerous graph problems in models such as LOCAL and CONGESTED-CLIQUE, with strong connections to the MPC model for parallel computing. Dr. Fischer introduced new techniques for distributed algorithm design, as well as for the analysis of randomized algorithms for graph problems. Two of the results presented in her thesis resolve central problems that were open for over 25 years: the first efficient deterministic distributed algorithm for $(2\Delta-1)$-edge-coloring, and a tight analysis of a randomized greedy MIS algorithm. The thesis is technically broad and deep, spanning at least five intrinsically different technical challenges: (1) rounding for linear programs, (2) bootstrapping Lovasz Local Lemma algorithms, (3) analyzing an intricate stochastic process, (4) bounding convergence of a Markov chain via path coupling, and (5) a number of randomized ideas in massively parallel computation. Dr. Fischer’s techniques have already been adopted by the leading researchers in the field, and are used in several follow-up works.
The award is sponsored jointly by the ACM Symposium on Principles of Distributed Computing (PODC) and the EATCS Symposium on Distributed Computing (DISC). It is presented annually, with the presentation taking place alternately at PODC and DISC. This year it will be presented at DISC, to be held at Augusta, Georgia USA, October 25-27, 2022.
The 2022 Award Committee:
- Yehuda Afek (chair), Tel-Aviv University
- Keren Censor-Hillel, Technion
- Pierre Fraigniaud, CNRS and Université Paris Cité
- Seth Gilbert, National University of Singapore
- Gopal Pandurangan, University of Houston
- Gadi Taubenfeld, Reichman University, Herzliya
