Recent developments in quantum distributed computing<\/em><\/strong>
October 28, 2025 at 10:00
<\/p>\n\n\n
![\"\"](\"http:\/\/www.disc-conference.org\/wp\/disc2025\/files\/2025\/10\/legall-Nagoya-HR-s.jpg\")
<\/figure>\n<\/div>\n\n\nBio:<\/strong> Fran\u00e7ois 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.<\/p>\n\n\n\n Title:<\/strong> Recent developments in quantum distributed computing<\/p>\n\n\n\n Abstract: <\/strong>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.<\/p>\n\n\n\n Keynote 2: Moni Naor, Weizmann Institute of Science, Israel <\/strong> Bio:<\/strong> 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\u2019s 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. Title: <\/strong>What Can Be Computed and Verified Locally: A Three Decade Perspective<\/p>\n\n\n\n Abstract:<\/strong> 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).<\/p>\n\n\n\n In our early work, we considered several questions, including:<\/p>\n\n\n\n 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.<\/p>\n\n\n\n Keynote 3: Ittai Abraham, Intel Labs, Israel Bio:<\/strong> 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.<\/p>\n\n\n\n Title:<\/strong> Open Questions and Future Challenges in Fault Tolerant Distributed Computing The Program Committee of DISC 2025 has selected the following paper to receive the DISC 2025 Best Paper Award<\/strong>:<\/p>\n\n\n\n Complexity landscape for local certification<\/strong> 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.<\/p>\n\n\n\n The Program Committee of DISC 2025 has selected the following papers to share the and<\/em> The Program Committee has also decided to highlight the following papers, selected across major areas of DISC\u2019s scope:<\/p>\n\n\n\n Keynotes Keynote 1: Fran\u00e7ois Le Gall, Nagoya University, JapanRecent developments in quantum distributed computingOctober 28, 2025 at 10:00 Bio: Fran\u00e7ois Le Gall is a Professor in the Graduate School of Mathematics, Nagoya University. He did his undergraduate studies in France … Continue reading
\n\n\n\n
(on behalf of the winners of the 2025 Dijkstra Prize<\/a>)<\/strong>
What Can Be Computed and Verified Locally: A Three Decade Perspective<\/em><\/strong>
October 29, 2025 at 10:00<\/p>\n\n\n![\"\"](\"https:\/\/www.disc-conference.org\/wp\/disc2025\/files\/2025\/10\/moni-naor-1-958x1024.jpg\")
<\/figure>\n<\/div>\n\n\n
His prizes and honors include the G\u00f6del Prize by ACM SIGACT for the notion of Instance Optimality and its applications (ACM\/SIGACT) (2014), the Paris Kanellakis Award of the ACM\u2019s (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.<\/p>\n\n\n\n\n
\n\n\n\n
Open Questions and Future Challenges in Fault Tolerant Distributed Computing<\/em><\/strong>
October 30, 2025 at 10:00<\/p>\n\n\n![\"\"](\"https:\/\/www.disc-conference.org\/wp\/disc2025\/files\/2025\/10\/Ittai-images.jpeg\")
<\/figure>\n<\/div>\n\n\n
Abstract.<\/strong> 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\u2019s 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.<\/p>\n\n\n\nAwards and Highlights<\/h2>\n\n\n\n
by Nicolas Bousquet, Laurent Feuilloley, and S\u00e9bastien Zeitoun.<\/p>\n\n\n\n
\n\n\n\n
DISC 2025 Best Student Paper Award<\/strong>:<\/p>\n\n\n\n
Content-Oblivious Leader Election in 2-Edge-Connected Networks<\/strong>
by J\u00e9r\u00e9mie Chalopin, Yi-Jun Chang, Lyuting Chen, Giuseppe A. Di Luna, and Haoran Zhou<\/p>\n\n\n\n
pod: An Optimal-Latency, Censorship-Free, and Accountable Generalized
Consensus Layer<\/strong>
by Orestis Alpos, Bernardo David, Jakov Mitrovski, Odysseas Sofikitis, and Dionysis Zindros.<\/p>\n\n\n\n
Lyuting Chen and Haoran Zhou (first paper) and Jakov Mitrovski (second paper) are the
student co-authors receiving the shared award.
The paper \u201cContent-Oblivious Leader Election in 2-Edge-Connected Networks\u201d 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 \u201cpod: An Optimal-Latency, Censorship-Free, and Accountable Generalized
Consensus Layer\u201d 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 \u2013 such as auctions and payment systems
<\/p>\n\n\n\n
\n\n\n\n\n