Danupon Nanongkai erhält den Edsger W. Dijkstra-Preis für Verteiltes Rechnen

Direktor Danupon Nanongkai ist einer der Preistzräger des 2026er Dijkstra-Preises für verteilte Systeme. Foto: MPI-INF

Der Edsger W. Dijkstra-Preis für verteiltes Rechnen (Distributed Computing) geht an ein internationales Forscherteam für ihre wegweisende Arbeit aus dem Jahr 2011 mit dem Titel: „Distributed Verification and Hardness of Distributed Approximation“. Unter den Preisträgern ist Danupon Nanongkai, Direktor der Abteilung „Algorithms and Complexity“ am Max-Planck-Institut für Informatik.

Der Preis wird gemeinsam vom „ACM Symposium on Principles of Distributed Computing (PODC)“ und dem „EATCS Symposium on Distributed Computing (DISC)“ vergeben und ehrt Arbeiten, die über mindestens ein Jahrzehnt hinweg einen bedeutenden Einfluss auf die Theorie und Praxis des verteilten Rechnens ausgeübt haben. Ausgezeichnet werden in diesem Jahr Atish Das Sarma, Stephan Holzer, Liah Kor, Amos Korman, Danupon Nanongkai, Gopal Pandurangan, David Peleg und Roger Wattenhofer. Ihre Studie zeigt, dass bei verteilten Netzwerkberechnungen (Graphen) die Datenübertragung zwischen den einzelnen Rechnern den maßgeblichen Engpass bildet. Die Systemleistung hängt somit hauptsächlich von der verfügbaren Bandbreite ab – ein Ergebnis, das die moderne Theorie des bandbreitenlimitierten verteilten Rechnens geprägt hat, wie es in der Preisbegründung heißt.

Ursprünglich 2011 auf dem ACM Symposium on Theory of Computing (STOC) veröffentlicht und später 2012 im SIAM Journal on Computing erschienen, führte die Arbeit ein Framework ein, um grundlegende Grenzen im Bereich verteiltes Rechnen (eine Methode, bei der mehrere Rechner als eine Einheit agieren) zu bestimmen. Durch die Verbindung von Kommunikationstheorie und Netzwerkverifikation entwickelten die Autoren einen systematischen Ansatz, um theoretische Mindestlaufzeiten zu beweisen, die zur Lösung verschiedener Probleme erforderlich sind. Dies galt für viele zentrale Aufgaben, wie das Finden kürzester Pfade (shortest path problem) oder minimaler Anteile (minimal cut). Heute sind diese Methoden Standardwerkzeuge im Fachgebiet. Darüber hinaus haben die in der Arbeit vorgestellten Erkenntnisse die weitere Forschung geprägt, etwa durch die Erweiterung des Frameworks auf neue Probleme und die Entwicklung von Algorithmen, die an die neue definierten Grenzen heranreichen. 

Das Dijkstra-Preis-Komitee 2026 setzt sich zusammen aus James Aspnes (Yale University), Keren Censor-Hillel (Technion), Cyril Gavoille (Universität Bordeaux), Seth Gilbert (National University of Singapore), Andrzej Pelc (Université du Québec en Outaouais) und Eric Ruppert (York University). Die Preisverleihung findet auf der PODC 2026 statt.

Danupon Nanongkai ist seit 2022 Wissenschaftlicher Direktor am Max-Planck-Institut für Informatik in Saarbrücken, wo er die Abteilung Algorithmen und Komplexität leitet. Er promovierte 2011 in Algorithmen, Kombinatorik und Optimierung (ACO) am Georgia Institute of Technology und habilitierte sich 2017 in Informatik an der KTH Royal Institute of Technology in Schweden.

Seine Forschung konzentriert sich auf Graphalgorithmen und Berechnungskomplexität, mit besonderem Interesse an der Entwicklung algorithmischer Techniken, die in verschiedenen Berechnungsmodellen effektiv einsetzbar sind. Er hat zu effizienten Algorithmen für grundlegende Graphprobleme wie Zusammenhang und Abstände beigetragen – von sequenziellen über verteilte bis hin zu dynamischen Algorithmen.

Weitere Informationen:
Bekanntgabe des PODC/DISC: https://www.podc.org/2026-edsger-w-dijkstra-prize-in-distributed-computing/
Webseite der Abteilung Algorithms and Complexity: https://www.mpi-inf.mpg.de/de/departments/algorithms-complexity

Redaktion:
Philipp Zapf-Schramm
Max-Planck-Institut für Informatik
Tel: +49 681 9325 4509
E-Mail: pzs@mpi-inf.mpg.de