Awards

It is our pleasure to award the 2023 SIROCCO Prize for Innovation in Distributed Computing to Boaz Patt-Shamir, professor at Tel-Aviv University, Israel, for his outstanding contributions to distributed computing under bandwidth limitations.

Boaz Patt-Shamir is one of the main contributors to distributed network computing, especially regarding solving graph problems efficiently under the constraint that nodes can exchange a limited information with their neighbors in each round. Typical problems addressed in Boaz Patt-Shamir’s papers are routing, matching, shortest paths, sorting, and checkability, to mention just a few. They also include problems motivated by applications such as sensor networks, recommendation systems, peer-to-peer applications, etc.
At the beginning of the 2000s, Boaz Patt-Shamir co-authored two breakthrough papers, namely:

• Zvi Lotker, Boaz Patt-Shamir, David Peleg: Distributed MST for constant diameter graphs. In Proc. of 20th ACM Symposium on Principles of Distributed Computing (PODC 2001).
• Zvi Lotker, Elan Pavlov, Boaz Patt-Shamir, David Peleg: MST construction in O(log log n) communication rounds. In Proc. of 15th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2003).

Indeed, since the work by J. Garay, S. Kutten, D. Peleg, and V. Rubinovich (SIAM J. of Computing, 1998 and 2000), it was known that constructing a minimum-weight spanning tree (MST) can be done in roughly O(D + √n) rounds in n-node networks with diameter D =  Ω (log n) when the nodes are restricted to exchange O(log n)-bit messages in each round. It was also known that this bound is essentially tight. In his PODC 2001 paper, Boaz Patt-Shamir et al. proved that an n^Ω(1) lower bound also holds in networks with constant diameter, specifically Õ(√n) rounds in networks with diameter 4, and Õ(n^1/4) rounds in networks with diameter 3. In contrast, the same paper shows that, in graphs with diameter 2, MST can be solved in O(log n) rounds, hence establishing an exponential gap between the computing power of networks with diameter 3 and those with diameter 2. Another exponential gap is established in the SPAA 2003 paper, in which Boaz Patt- Shamir et al. proved that MST can be solved in just O(loglogn) rounds in cliques. The model introduced in the SPAA 2003 paper is now commonly referred to as the Congested Clique model, which completes the trio of core models for distributed network computing, now known as LOCAL, CONGEST, and Congested Clique.
The Congested Clique model enables to focus solely on the impact of congestion caused by narrow communication links, putting aside effects caused by the distance between nodes, and, more generally, by the structure of the network. As such, the Congested Clique model is an elegant, flexible, and fruitful abstraction enabling to understand the power and limitation of computing with limited communication resources. Non surprisingly, the SPAA paper introducing the Congested Clique model had a huge impact on research in the framework of principles of distributed computing — it was cited more than a hundred of times. Last but not least, the Congested Clique model links together distributed and parallel computing, thanks to its close connections to the Massively Parallel Computation (MPC) model, which emerged in the years 2008–2012 owing to the deployment of popular computing platforms such as MapReduce and Hadoop.
For its participation to the discovery of the Congested Clique model, and for all his contributions to distributed computing in models constrained by bandwidth limitations such as Congested Clique, CONGEST, sensor networks, etc., Boaz Patt-Shamir fully deserves to be recognized by the distributed computing community as one of its prominent members.

The 2023 Award committee:¹

Paola Flocchini (University of Ottawa, Canada)
Magnús M. Halldórsson (Reykjavik University, Iceland)
Tomasz Jurdziński (University of Wroclaw, Poland)
Zvi Lotker (Ben-Gurion University of the Negev, Israel)
Merav Parter (Weizmann Institute, Israel)
Andréa W. Richa (Arizona State University, USA)
Stefan Schmid (Technical University of Berlin, Germany)

¹ We wish to thank the nominators for the nomination and for contributing heavily to this text.