SIROCCO 2017

Laudatio

It is a pleasure to award the 2017 SIROCCO Prize for Innovation in Distributed Computing to Shmuel Zaks. Shmuel’s contributions span an impressive range of research areas in Computer Science and Discrete Mathematics, including classical Distributed Computing (leader election, combinatorial and graph problems, complexity, impossibility, compact routing, self-stabilization, and more) and Networking. Shmuel’s work on Networking has been performed during the last three decades; the first half of this period was devoted to ATM networks, and the second to optical networks.

The prize is awarded for these lifetime achievements of his, but especially for pioneering research on algorithmic aspects of optical networks. In his seminal studies Shmuel formulated new problems and identified new research directions. The problems under investigation deal with a variety of aspects of optimization of the switching cost in the network, measured by the use of ADMs (ADD-DROP Multiplexers) and regenerators. Shmuel’s studies deal with all algorithmic aspects of optimization problems that stem from optical networks, including the design and analysis of algorithms (e.g., approximation algorithms and on-line algorithms), complexity, parameterized complexity and inapproximability. Shmuel’s work initiated systematic studies of a variety of problems where mostly heuristics and simulations were previously used.

Examples of areas in which Shmuel’s contributions to algorithmic aspects of optical networks are the most important include: ADM minimization [1,2], regenerator placement [3,4], traffic grooming [5], and the flex-grid model [6], where a lightpath has to be assigned a number of colors, within a contiguous or a non-contiguous range.

The 2017 Award committee:

Paola Flocchini (University of Ottawa)
Magnús M. Haldórsson (University of Reykjavik)
Thomas Moscibroda (Microsoft Research)
Andrzej Pelc, chair (Université du Québec en Outaouais)
Christian Scheideler (University of Paderborn)

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

References

Selected publications related to Shmuel Zaks’ contribution:

1. Tamar Eilam, Shlomo Moran and Shmuel Zaks, Lightpath Arrangement in Survivable Rings to Minimize the Switching Cost, IEEE Journal on Selected Areas in Communications (JSAC), special issue on WDM-based network architectures, 20(1), January 2002, pp. 172-182.
2. Tamar Eilam, Shlomo Moran and Shmuel Zaks, Approximation Algorithms for Survivable Optical Networks, Proceedings of the 14th International Workshop on Distributed Algorithms (DISC), Toledo, Spain, October 2000, pp. 104-118.
3. Michele Flammini, Alberto Marchetti Spaccamela, Gianpiero Monaco, Luca Moscardelli and Shmuel Zaks, On the Complexity of Placement of Regenerators in Optical Networks, Proc. 21st ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), Calgary, Canada, August 2009, pp. 154-162.
4. George B. Mertzios, Ignasi Sau, Mordechai Shalom and Shmuel Zaks, Placing Regenerators in Optical Networks to Satisfy Multiple Sets of Requests, Proc. 37th International Colloquium on Automata, Languages and Programming (ICALP), Bordeaux, France, July 2010, pp. 333-344. Best paper award.
5. Ignasi Sau, Mordechai Shalom and Shmuel Zaks, Traffic Grooming in Star Networks via Matching Techniques, Proc. 17th International Colloquium on Structural Information and Communication Complexity (SIROCCO), Nesin Mathematics Village, Şirince, Turkey, June 2010, pp. 41-56.
6. Mordechai Shalom, Prudence W.H.Wong and Shmuel Zaks, Profit Maximization in Flex-Grid All-Optical Networks, Proc. 20th International Colloquium on Structural Information and Communication Complexity (SIROCCO), Ischia, Italy, July 2013, pp. 249-260.