The committee for the 2024 Principles of Distributed Computing Doctoral Dissertation Award has decided to share the award between two recipients:
- Dr. Robin Vacus for his dissertation “Algorithmic Perspectives to Collective Natural Phenomena.”
- Dr. Yuanhao Wei for his dissertation “General Techniques for Efficient Concurrent Data Structures.”
Dr. Vacus completed his PhD under the supervision of Amos Korman and Pierre Fraigniaud, at the Université Paris Cité. His thesis applies a distributed systems approach to problems and models inspired by biology and sociology. The first part of the thesis considers solutions to two agreement-related problems in a setting in which agents have very limited resources, as one would expect in an algorithm that may be executed by animals or even biological cells. It starts by studying a “bit dissemination” problem in which the agents need to decide among two alternatives. Each starts with an opinion but only one of the agents knows the correct choice and will insist on it. Agents exchange opinions with a small sample of peers. The analysis shows an exponential gap between convergence times in the case in which agents move simultaneously vs. moving sequentially, and a similar gap between memoryless solutions and ones that employ strong separation between the simultaneous and the sequential activation models, and between memory-less solutions and ones in which agents use a small amount of memory. The next problem tackled in this part involves a continuous setting, in which agents try to come as close to their center of mass as possible, while they suffer from Gaussian drift over time and from noisy distance measurements. Somewhat unexpectedly, it is shown that an algorithm using all-to-all communication is not significantly better than one that employs no communication whatsoever.
The second part of the thesis considers the role and impact of altruism vs free riding on cooperation in a game-theoretic setting. In one game, it is shown that players’ motivation to work to increase their payoffs can sometimes be positively be affected by the amount of easily accessible resources (“low hanging fruit”), while in other cases it may be negatively correlated
to that amount.
The final question studied in the thesis is a variant of the “tragedy-of-the-commons” in which besides cooperating or defecting players may opt to behave hypocritically, meaning that they perform the least amount of work needed in order to appear to be cooperating. An original mechanism that uses moderate social pressure on non-cooperators is shown to cause defectors to be more cooperative. Dr. Vacus’ thesis provides an inspiring overview of the questions
studied, and employs a wide range of tools and techniques, involving probabilistic analysis, control theory, statistics and game theory, and computer simulations.
Dr. Wei completed his PhD under the supervision of Prof. Guy E. Blelloch, at MU. In his thesis, Dr. Wei proposes general techniques for improving existing concurrent data structures by simplifying their design and enhancing their performance. The goal of the thesis is to offer techniques that are easy to use to non-experts, even though their implementation behind-the-scenes is complicated and subtle. The techniques presented in the thesis are: (a) Lock-free locks, an automated and general method for converting lock-based concurrent code into lock-free code, requiring no involvement from the programmer; (b) Consistent snapshots: a method for enriching any data structure with a linearizable snapshot operation, which provides a global
copy of the state of the object as it existed at some point during the snapshot operation; and (c) Safe memory reclamation: a combination of manual safe-memory reclamation and automated reference counting, which is simpler than existing techniques, and is shown to be competitive in its performance. The thesis also includes implementations and a rigorous empirical evaluation
of the techniques it contributes, including applications to a variety of concurrent data structures.
The implementations are offered as libraries which are freely available to the public. Given the growing importance of concurrency, and the well-known difficulty of writing correct and efficient concurrent code, the thesis is well-poised to find practical impact in the programming world.
The 2024 Principles of Distributed Computing Doctoral Dissertation Award Committee:
- Magnús M. Halldórsson, Reykjavik University
- Yoram Moses (chair), Technion
- Rotem Oshman, Tel-Aviv University
- Paul Spirakis, University of Liverpool and University of Patras