Keynotes
Keynote 1: François Le Gall, Nagoya University, Japan
Recent developments in quantum distributed computing
October 28, 2025 at 10:00
Bio: François Le Gall is a Professor in the Graduate School of Mathematics, Nagoya University. He did his undergraduate studies in France and received his PhD in 2006 from the University of Tokyo. His research interests include algorithms, computational complexity and quantum computation. In the past few years he has been working on the design of quantum distributed algorithms.
Title: Recent developments in quantum distributed computing
Abstract: I will talk about quantum distributed computing, i.e., distributed computing where the processors of the network can exchange quantum messages. After describing the basics of quantum computing, I will present recent developments in quantum distributed algorithms that show a significant quantum advantage for some distributed computing tasks. I will also describe interesting and important open questions in quantum distributed computing.
Keynote 2: Moni Naor, Weizmann Institute of Science, Israel
(on behalf of the winners of the 2025 Dijkstra Prize)
What Can Be Computed and Verified Locally: A Three Decade Perspective
October 29, 2025 at 10:00
Bio: Moni Naor is a professor of Computer Science who explores the foundations of computer science, particularly cryptography and privacy. He studied Computer Science at the Technion and received his PhD from the University of California Berkeley under the supervision of Professor Manuel Blum. He was then a researcher at IBM’s Almaden Research Center for four years, where he collaborated with Larry Stockmeyer. He joined the Weizmann Institute faculty in 1993. He is the incumbent of the Judith Kleeman Professorial Chair.
His prizes and honors include the Gödel Prize by ACM SIGACT for the notion of Instance Optimality and its applications (ACM/SIGACT) (2014), the Paris Kanellakis Award of the ACM’s (2016) for Broadcast Encryption and Traitor Tracing, the Alberto O. Mendelzon Test-of-Time Award (2011), the STOC Test-of-Time Award for the work on Non-Malleability, the IACR RSA Award for Excellence in Mathematics (2022) the Rothchild Prize in 2024. Professor Naor is a Fellow of the International Association of Cryptologic Research and the ACM.
Title: What Can Be Computed and Verified Locally: A Three Decade Perspective
Abstract: Three decades ago, the late Larry Stockmeyer and I embarked on exploring what can be computed locally in a distributed network. In this context, “local” refers to tasks that can be completed within time or distance that is independent of the overall size of the network. In particular we investigated Locally Checkable Labeling (LCL) problems, where the validity of a labeling can be verified through local interactions (e.g., graph coloring).
In our early work, we considered several questions, including:
- Are there interesting examples of LCLs solvable in a local manner?
- Is there a way to determine whether an LCL is locally solvable?
- What role do randomized algorithms play in this space?
In this talk, I will revisit these foundational questions, share the journey that led us to consider these questions, and highlight key developments in the theory of local computation since then. We will explore how these ideas have evolved and shaped new directions in distributed computing.
Keynote 3: Ittai Abraham, Intel Labs, Israel
Open Questions and Future Challenges in Fault Tolerant Distributed Computing
October 30, 2025 at 10:00
Bio: Ittai Abraham does research in algorithms and distributed computing. He received his PhD from the Hebrew University of Jerusalem and has spent nearly two decades in industrial research, first at Microsoft Research Silicon Valley and then as a founding member of the VMware Research Group, where he later established its branch in Israel. He is currently a researcher at Intel Labs.
Title: Open Questions and Future Challenges in Fault Tolerant Distributed Computing
Abstract. In this talk, I will survey some of my favorite open questions in fault tolerant distributed computing and discuss the challenges that are likely to shape the field’s future. I will highlight foundational mathematical problems, broader conceptual directions, and the connections between theory and practice, with the goal of sparking discussion on where the next breakthroughs may emerge.
Awards and Highlights
The Program Committee of DISC 2025 has selected the following paper to receive the DISC 2025 Best Paper Award:
Complexity landscape for local certification
by Nicolas Bousquet, Laurent Feuilloley, and Sébastien Zeitoun.
One of the most intensively studied topics in distributed graph algorithms in recent years has been to determine the complexity landscape of LCL problems, culminating in an almost complete classification of the asymptotic time complexities that LCL problems can exhibit, on both general (bounded-degree) graphs and more restricted graph classes such as paths or trees. The work awarded the DISC 2025 best paper award initiates the study of a distributed space complexity landscape, more precisely, the landscape of certificate space complexity in local certification. Besides opening the door to a possibly similarly fruitful line of research as for the aforementioned time complexity landscape, the paper comes with a variety of insightful and surprising results, charting considerable parts of the unknown landscape regimes in different settings. These results range from complexity gap results, showing that no graph property exhibits an optimal certificate space complexity contained in the respectively considered gap, to existence results proving that, for certain space complexities, the properties exhibiting such space complexities exist. The proofs of these results are obtained via an automata-theoretic approach that features a number of novel and clean ideas and differs significantly from the usage of automata theory in the study of the time complexity of LCL problems. The paper also provides several interesting open questions, highlighting the potential this line of research has to offer.
The Program Committee of DISC 2025 has selected the following papers to share the
DISC 2025 Best Student Paper Award:
Content-Oblivious Leader Election in 2-Edge-Connected Networks
by Jérémie Chalopin, Yi-Jun Chang, Lyuting Chen, Giuseppe A. Di Luna, and Haoran Zhou
and
pod: An Optimal-Latency, Censorship-Free, and Accountable Generalized
Consensus Layer
by Orestis Alpos, Bernardo David, Jakov Mitrovski, Odysseas Sofikitis, and Dionysis Zindros.
Lyuting Chen and Haoran Zhou (first paper) and Jakov Mitrovski (second paper) are the
student co-authors receiving the shared award.
The paper “Content-Oblivious Leader Election in 2-Edge-Connected Networks” makes two fundamental contributions to the design of content-oblivious leader election algorithms over asynchronous networks. The first result is a (non-uniform) deterministic leader election algorithm for general 2-edge-connected graphs, thereby enabling the simulation of arbitrary distributed algorithms without a preselected leader in this model. The second result is a uniform, quiescently terminating deterministic leader election algorithm for unoriented rings, showing that this task is possible even when the ring is unoriented and without requiring additional knowledge. These two results represent a significant advancement in understanding leader election algorithms in content-oblivious asynchronous networks, conjectured to be impossible in the general case (i.e., for uniform algorithms over any 2-edge-connected graph)
The paper “pod: An Optimal-Latency, Censorship-Free, and Accountable Generalized
Consensus Layer” introduces Pod, a novel consensus primitive designed to achieve optimal latency, specifically targeting one network round-trip for transaction confirmation. Unlike traditional consensus protocols that depend on inter-replica communication and total-order guarantees, Pod emphasizes low latency, censorship resistance, and accountability. A key safety guarantee is the past-perfection property, which gives clients a stable view of the past: once a round becomes past-perfect, no new confirmed transactions can appear before it. Thus, pod trades off traditional agreement properties in favor of optimal latency, while maintaining sufficient security guarantees to support distributed tasks that do not require total order – such as auctions and payment systems
The Program Committee has also decided to highlight the following papers, selected across major areas of DISC’s scope:
- Team Formation and Applications, by Yuval Emek, Shay Kutten, Ido Rafael, and Gadi Taubenfeld
- Approach of Agents with Restricted Fuel Tanks, by Adam Ganczorz, Tomasz Jurdzinski, Andrzej Pelc, and Grzegorz Stachowiak
- Two for One, One for All: Deterministic LDC-based Robust Computation in Congested Clique, by Keren Censor-Hillel, Orr Fischer, Ran Gelles, and Pedro Soto
- Validity in Network-Agnostic Byzantine Agreement, by Andrei Constantinescu, Marc Dufay, Diana Ghinea, and Roger Wattenhofer
- Distributed Download from an External Data Source in Byzantine Majority Settings, by John Augustine, Soumyottam Chatterjee, Valerie King, Manish Kumar, Shachar Meir, and David Peleg
- Strong Linearizability without Compare&Swap: The Case of Bags, by Faith Ellen and Gal Sela
- Towards Optimal Distributed Edge Coloring with Fewer Colors, by Manuel Jakob, Yannic Maus, and Florian Schager
- On the Randomized Locality of Matching Problems in Regular Graphs, by Seri Khoury, Manish Purohit, Aaron Schild, and Joshua R. Wang
- Distributed Computation with Local Advice, by Alkida Balliu, Sebastian Brandt, Fabian Kuhn, Krzysztof Nowicki, Dennis Olivetti, Eva Rotenberg, and Jukka Suomela