28th International Colloquium on Structural Information and Communication Complexity
 
SIROCCO 2021

2021 SIROCCO Prize for Innovation in Distributed Computing

Prof. Friedhelm Meyer auf der Heide

Heinz Nixdorf Institut
Universität Paderborn

Laudatio

It is a pleasure to award the 2021 SIROCCO Prize for Innovation in Distributed Computing to Friedhelm Meyer auf der Heide. Friedhelm has been an active contributor to the field of Distributed Computing since its very beginning, with pioneering contributions to online scheduling problems, load balancing, distributed data structures, hashing, network routing, mobile facility location and distributed data streams. Not only has he produced excellent research on distributed computing, but has also inspired and mentored several young researchers some of whom are now well established scientists in this field. His numerous research contributions includes seven articles in SIROCCO and a keynote lecture.

The prize is awarded for his contributions to continuous strategies for swarms of mobile robots. The decentralized coordination of large teams of mobile robots has been a key research theme is this community, but primarily with the simplifying assumption that robots act only at discrete times. This discrete time model and its variations have been canonical in the research on distributed mobile robotics. Friedhelm advocated the unorthodox model of continuous protocols [8] where robots observe their surroundings and execute the protocol continuously while they are moving. Such a model requires completely different set of tools for analyzing robot protocols and proving their correctness and efficiency. This model was first presented in the SIROCCO 2010 paper [1] which considers continuous strategies for line formation by mobile robots with limited vision. Subsequent papers adressed the fundamental problem of gathering and its other variants [4,6,7] in the same model, thus establishing the utility of this new model.

Another important contribution of Friedhelm is the introduction of new techniques for analyzing well-known algorithms for mobile robots which, among other results, provided an asymptotically optimal time bound for the classical convergence algorithm [3] and a tight bound for the first known gathering algorithm in the limited visibility model [2]. Yet another novel contribution of Friedhelm is the consideration of energy-efficient strategies for mobile robot formation problems in the continuous plane [5].

The model proposed and studied in detail by Friedhelm and his coauthors has two key features: limited visibility of robots and continuous motion, which brings it closer to the research performed by the robotics community as well as control theory researchers, thus bridging the gap between three different communities of researchers who work on mobile robots. With his co-authors, Friedhelm is already extending his work to the three dimensional case, presenting the first gathering algorithm for robots moving continuously in the 3D space in an article [9] that received the best student paper award at SIROCCO 2020. We believe Friedhelm’s contributions will continue to inspire young researchers to work in this emerging area of distributed computing.

The 2021 Award committee

  • Keren Censor-Hillel (Technion)
  • Shantanu Das (Aix-Marseille Université)
  • Michele Flammini (Gran Sasso Science Institute)
  • ‪Magnús M. Halldórsson, chair (Reykjavik University)
  • Zvi Lotker (Ben Gurion University of the Negev)
  • Boaz Patt-Shamir (Tel Aviv University)
  • Sébastien Tixeuil (Sorbonne Université)

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

Selected publications related to Friedhelm Meyer auf der Heide’s Contribution:

  1. B. Degener, B. Kempkes, P. Kling, F. Meyer auf der Heide, A Continuous, Local Strategy for Constructing a Short Chain of Mobile Robots. Proc. SIROCCO 2010: 168-182.
  2. B. Degener, B. Kempkes, T. Langner, F. Meyer auf der Heide, P. Pietrzyk, R. Wattenhofer, A tight runtime bound for synchronous gathering of autonomous robots with limited visibility. Proc. SPAA 2011: 139-148.
  3. A. Cord-Landwehr, B. Degener, M. Fischer, M. Hüllmann, B. Kempkes, A. Klaas, P. Kling, S. Kurras, M. Märtens, F. Meyer auf der Heide, C. Raupach, K. Swierkot, D. Warner, C. Weddemann, D. Wonisch, A New Approach for Analyzing Convergence Algorithms for Mobile Robots. Proc. ICALP(2) 2011: 650-661.
  4. B. Kempkes, P. Kling, F. Meyer auf der Heide, Optimal and Competitive runtime bounds for continuous, local gathering of mobile robots. Proc. SPAA 2012: 18-26.
  5. P. Brandes, B. Degener, B. Kempkes, F. Meyer auf der Heide: Energy-efficient Strategies for Building Short Chains of Mobile Robots Locally, Theoretical Computer Science, 509: 97-112 (2013).
  6. B. Degener, B. Kempkes, P. Kling, F. Meyer auf der Heide: Linear and Competitive Strategies for Continuous Robot Formation Problems. ACM Transactions on Parallel Computing, 2(1):2:1-2:18 (2015).
  7. S. Li, C. Markarian, F. Meyer auf der Heide, P. Podlipyan, A Continuous Strategy for Collisionless Gathering. Proc. ALGOSENSORS 2017: 182-197.
  8. P. Kling, F. Meyer auf der Heide, Continuous Protocols for Swarm Robotics, In: Distributed Computing by Mobile Entities, Current Research in Moving and Computing, 317-334 (2019).
  9. M. Braun, J. Castenow, F. Meyer auf der Heide, Local Gathering of Mobile Robots in Three Dimensions. Proc. SIROCCO 2020: 63-79.