It is a pleasure to award the 2018 SIROCCO Prize for Innovation in Distributed Computing to Zvi Lotker. Zvi is one of the main actors in distributed computing and the author of many breakthrough results concerning network algorithms. In particular, his PODC 2001 and SPAA 2003 papers on MST construction in sub-logarithmic number of rounds yielded an enormous amount of subsequent research and helped to establish the CONGEST model and the Congested Clique model as core models in distributed network computing. He had important contributions to the buffer management in network switches in his STOC 2001 and PODC 2002 papers, as well as distributed approximate matching (PODC 2007 and SPAA 2008) and random walk analysis (SPAA 2008).

The award is given for these life-time achievements of Zvi in network algorithms, but especially for his creative contributions to the theory of wireless and social networks. In wireless networks his results range from network synchronization based on stolen signals (SIROCCO 2011) to directional antennas (SIROCCO 2013) and the topology of wireless communication in the SINR model (STOC 2011). Zvi’s contributions to the theory of social networks are equally impressive and range from the small world phenomenon, as in his SIROCCO 2008 paper, to homophily and the glass ceiling effect in social networks (ITCS 2015) and core-periphery networks (ICALP 2014). Last but not least, Zvi Lotker launched recently a project on studying social networks through the analysis of Shakespeare’s theatre plays from the perspective of interactions between the characters. An example of this work is his ASONAM 2016 paper.

To summarize, Zvi’s main characteristics as a scientist are creativity, imagination and an unorthodox approach to research problems, combined with deep technical knowledge of distributed computing and networks. Since his main achievements are in the core areas of interest of SIROCCO, he is an excellent fit for the Prize for Innovation in Distributed Computing.

The 2018 Award committee¹

• Magnu's M. Halldorsson (Reykjavik University)
• Andrzej Pelc, chair (Universite du Quebec en Outaouais)
• Christian Scheideler (University of Paderborn)
• Paul Spirakis (University of Liverpool)
• Jukka Suomela (Aalto University)

Selected publications related to Zvi Lotker’s contribution:

1. Gady Kozma, Zvi Lotker, Micha Sharir, Gideon Stupp: Geometrically aware communication in random wireless networks. PODC 2004: 310-319
2. Zvi Lotker, Boaz Patt-Shamir, David Peleg: Distributed MST for constant diameter graphs. Distributed Computing 18(6): 453-460 (2006)
3. Erez Kantor, Zvi Lotker, Merav Parter, David Peleg: The topology of wireless communication. STOC 2011: 383-392
4. Christian Schindelhauer, Zvi Lotker, Johannes Wendeberg: Network Synchronization and Localization Based on Stolen Signals. SIROCCO 2011: 294-305
5. Chen Avin, Yuval Emek, Erez Kantor, Zvi Lotker, David Peleg, Liam Roditty: SINR Diagrams: Convexity and Its Applications in Wireless Networks. J. ACM 59(4): 18:1-18:34 (2012)
6. Hadassa Daltrophe, Shlomi Dolev, Zvi Lotker: Probabilistic Connectivity Threshold for Directional Antenna Widths - (Extended Abstract). SIROCCO 2013: 225-236
7. Chen Avin, Barbara Keller, Zvi Lotker, Claire Mathieu, David Peleg, Yvonne Anne Pignolet: Homophily and the Glass Ceiling Effect in Social Networks. ITCS 2015: 41-50
8. Alkida Balliu, Pierre Fraigniaud, Zvi Lotker, Dennis Olivetti: Sparsifying Congested Cliques and Core-Periphery Networks. SIROCCO 2016: 307-322
9. Zvi Lotker: The tale of two clocks. ASONAM 2016: 768-776