Many exceptionally high-quality doctoral dissertations were submitted for the 2023 Principles of Distributed Computing
Doctoral Dissertation Award. After careful deliberation, the award committee decided to share the award between:

• Dr. Siddhartha Jayanti for his dissertation “Simple, Fast, Scalable, and Reliable Multiprocessor Algorithms.”

• Dr. Dean Leitersdorf for his dissertation “Fast Distributed Algorithms via Sparsity Awareness.”

Dr. Siddhartha Jayanti completed his PhD on November 27th 2022, under the supervision of Prof. Julian Shun, at MIT. In
his thesis, Dr. Jayanti identifies simplicity, speed, scalability, and reliability as four core design goals for multiprocessor
algorithms, and designs and analyzes algorithms that meet these goals. The thesis comprises a vast number of novel
results in the scope of distributed and concurrent synchronization. His algorithmic contributions include a scalable
algorithm for concurrent union-find, a wait-free linearizable, fast array data structure that supports standard array
operations in constant time and optimal space, and mutual exclusion (lock) algorithms with optimal complexity for
real-time and persistent memory systems. Dr. Jayanti also defines a generalization of the fundamental wake-up problem,
permitting him to prove fundamental new hardness results for many standard data structures, including queues, stacks,
priority queues, counters, and union-find data structures. Moreover, he devises a novel simple-to-use technique for
producing machine-verified proofs of the correctness (linearizability and strong linearizability) of concurrent algorithms,
and successfully applied this method to verify fundamental data multicore data structures, such as queues, union-find,
and snapshot objects.

Dr. Dean Leiterdorf completed his thesis on May 14th, 2022, under the supervision of Prof. Keren Censor-Hillel, at
the Technion. In his thesis, Dr. Leitersdorf designs fast distributed algorithms for sparse matrix multiplication and
demonstates their usefulness by applying them to shortest path and subgraph existence problems. Applications of
matrix multiplication are found in many fields, including scientific computing, statistics, machine learning, and quantum
computing, and therefore fast algorithms for matrix multiplication are critical for these. Dr. Leitersdorf does not
just come up with solutions that can exploit the sparsity of the input matrices but also the sparsity of the output
matrix, which allows him to come up with a large number of results for different communication models that partially
significantly improve the state of the art. Among these are constant-round algorithms for computing graph spanners and
approximate all-pairs-shortest-paths as well as constant-round algorithms for computing the girth of the input graph up
to an additive 1 in the Congested Clique model. Through reductions between various models and a number of advanced
techniques, Dr. Leitersdorf extends his results also to the CONGEST model, hybrid networks, and various other models.
On top of this, he also designs a variety of algorithms that speed up clique detection in quantum computing settings
and whose runtime breaks lower bounds known for classical distributed computing.

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 PODC, to be held in Orlando, Florida USA, June 19-23, 2023.
The 2023 Principles of Distributed Computing Doctoral Dissertation Award Committee

• Shlomi Dolev (Chair), BGU

• Rachid Guerraoui, EPFL
• Fabian Kuhn, University of Freiburg

• Woelfel Philipp, University of Calgary
• Christian Scheideler, Paderborn University