Sirocco Prize
2022 SIROCCO Prize for Innovation in Distributed Computing
Laudatio for Christian Scheideler
It is our pleasure to award the 2022 SIROCCO Prize for Innovation in Distributed Computing to Christian Scheideler, who is a professor at the University of Paderborn in Germany. Christian has contributed on a wide range of distributed computing topics, including distributed data structures and their algorithms, security in distributed systems, distributed randomized algorithms and stochastic processes, and network theory (in particular peer-to-peer systems, mobile ad-hoc networks and sensor networks). Christian has so far collected over 5700 citations, with one paper cited close to 600 times.
The prize is awarded for Christian's pioneering work on robust and efiicient overlay networks. The design and maintenance of efficient and robust overlay networks is one of the most fundamental and reoccurring themes in networking. Many distributed systems today rely on some kind of overlay network connecting the communicating nodes (or “peers”) of an application using logical links: e.g., distributed databases and data stores, publish-subscribe systems, file sharing systems such as BitTorrent, multimedia applications related to telephony and streaming (e.g., Skype), content distribution networks such as Akamai, crypto-currency infrastructures (e.g., Bitcoin), among many more. Many overlay networks are fairly transient and dynamic, with users joining and leaving according to content popularity or diurnal patterns. In addition, overlay networks are often characterized by an open membership, and hence need to account for malicious behavior.
Christian was among the first to recognize the importance of robustness and self-stabilization in the contecct of overlay networks and to provide rigorous algorithmic frameworks for their study. He is certainly one of the most influential authors in this area. Christian contributed several groundbreaking results on distributed algorithms for scalable overlay networks which support a seamless service (eg, routing) under continuous joins and leaves, and which “self-repair.” Of the many papers published by Christian on the topic, including three at SIROCCO [5, 2, 3], we highlight here three of his best-known and most-cited publications.
In Towards a Scalable and Robust DHT (ACM SPAA 2006 and Theory of Computing Systems 2009) [1], Christian and B. Awerbuch significantly advanced our understanding on how to render overlay networks and Distributed Hash Tables (DHTs) robust. While state-of-the-art DHTs at that time were at best robust to a constant (random) fraction of faulty peers, Christian and his co-author showed how to render DHTs robust to much more severe, adversarial failures: adaptive join-leave attacks in which an adversary can take over entire parts of the network (and e.g., eclipse honest peers), as well as adaptive insert and lookup attacks which imbalance the load. Their scalable join and leave protocols ensuring an even distribution were groundbreaking and inspired many future robust network designs.
Christian’s single-author How to spread adversarial nodes? Rotate! ACM STOC 2005 paper [6] presents an approach to keep a dynamic system of nodes well-mixed even under adversarial behavior: achieving such a well-mixed distribution is a crucial stepping stone for robust distributed systems, as it enables robust local decision making, even in the presence of significant adversarial behavior. The paper relies on a new and clever algorithm to join a peer-to-peer system. The algorithm presented by Christian is very efficient both in terms of the amount of randomness required, and in terms of the required rearrangements - both such features are attractive for actual deployment of the protocols. This paper hence presented an elegant, yet technically deep solution to a major open problem of that time. We believe that some of the ideas presented in this paper may become relevant also in the context of crypto-currency networks, which are currently becoming more sophisticated.
The paper A distributed polylogarithmic time algorithm for self-stabilizing skip graphs (ACM PODC 2009 and Journal of the ACM 2014) [4] represents a breakthrough in the design of self-stabilizing overlay networks. While the first self-stabilizing topologies were developed years before this paper, Christian and his co-authors were the first to present a self-stabilizing topology which is scalable: a topology with polylogarithmic degree and diameter, that supports efficient joins and leaves. Most importantly, the presented distributed algorithm self-stabilizes to the desired scalable network in a polylogarithmic number of rounds. The result remains a significant milestone in our understanding of topologically self-stabilizing algorithms, and of self-stabilizing algorithms in general.
Christian has also taken leadership roles in some of the main distributed computing conferences. Notably, he was Program Chair of SIROCCO 2015 and 2020 and Program Chair of the International Symposium on Distributed Computing (DISC) 2022, and Secretary and then General Chair of the ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2007-2020. He is an Associate Editor of the Journal of the ACM, among others.
The 2022 Award committee:1
- Keren Censor-Hillel (Technion, Israel)
- Michele Flammini (Gran Sasso Science Institute, Italy)
- Paola Flocchini (University of Ottawa, Canada)
- Magnus Halldórsson (Reykjavik University, Iceland)
- Tomasz Jurdziński (University of Wroclaw, Poland)
- Zvi Lotker (Ben-Gurion University of the Negev, Israel)
- Andréa W. Richa (Arizona State University, USA)
- Stefan Schmid (Technical University of Berlin, Germany)
References
[1] Baruch Awerbuch and Christian Scheideler. Towards a scalable and robust dht. Theory of Computing Systems, 45(2):234-260, 2009. A preliminary version of this paper appeared at ACM SPAA 2006.
[2] Jannik Castenow, Christina Kolb, and Christian Scheideler. A bounding box overlay for competitive routing in hybrid communication networks. In Proceedings of the 26th International Colloquium on Structural Information and Communication Complexity SIROCCO, pages 345-348, 2019.
[3] Thorsten Gotte, Kristian Hinnenthal, and Christian Scheideler. Faster construction of overlay networks. In Proceedings of the 26th International Colloquium Structural Information and Communication Complexity, SIROCCO, pages 262-276, 2019.
[4] Riko Jacob, Andréa W. Richa, Christian Scheideler, Stefan Schmid, and Hanjo Taubig. Skip+: A self- stabilizing skip graph. J. ACM, 61(6):36:1-36:26, 2014. A preliminary version of this paper appeared in ACM PODC’09.
[5] Sebastian Kniesburges, Andreas Koutsopoulos, and Christian Scheideler. A deterministic worst-case message complexity optimal solution for resource discovery. In Proceedings of Structural Information and Communication Complexity - 20th International Colloquium, SIROCCO, pages 165-176, 2013.
[6] Christian Scheideler. How to spread adversarial nodes?: Rotate! In Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing, pages 704-713. ACM, 2005.
1 We wish to thank the nominators for the nomination and for contributing heavily to this text.