Full papers
FEAT: Fair and Efficient Adversarial Transaction Ordering
Dakai Kang (University of California, Davis); Tien Tuan Anh Dinh (Deakin University); Mohammad Sadoghi (University of California, Davis)
The Power of Strong Linearizability: the Difficulty of Consistent Refereeing
Hagit Attiya (Technion); Armando Castañeda (Instituto de Matemáticas, Universidad Nacional Autónoma de México (UNAM)); Constantin Enea (Ecole Polytechnique, LIX)
Distributed Approximate Maximum Matching and Minimum Vertex Cover via Generalized Graph Decomposition
Peter Davies-Peck (Durham University)
Deterministic Distributed Algorithms for Short Disjoint Paths
Mohsen Ghaffari (MIT); Hsin-Hao Su (Boston College)
Ranking Opinions with Few States in Population Protocols
Tom-Lukas Breitkopf, Julien Dallot (TU Berlin); Antoine El-Hayek (Institute of Science and Technology Austria); Stefan Schmid (TU Berlin)
Distributed Renaming with Subquadratic Bits via Scalable Committee Election
Sirui Bai, Xinyu Fu (Nanjing University); Yuyi Wang (CRRC Zhuzhou Institute & Tengen Intelligence Institute); Chaodong Zheng (Nanjing University)
The Task Completion Problem and its Application to Crash-Resilient Computation
Orr Fischer, Ran Gelles (Bar-Ilan University)
Efficient Counting and Simulation in Content-Oblivious Rings
Jérémie Chalopin (CNRS, Aix-Marseille université); Yi-Jun Chang (National University of Singapore); Giuseppe Antonio Di Luna (Sapienza University); Haoran Zhou (National University of Singapore)
Reaching Univalency with Subquadratic Communication
Andrew Lewis-Pye (London School of Economics)
Undecided State Dynamics with Many Opinions
Colin Cooper, Frederik Mallmann-Trenn, Tomasz Radzik (King’s College London); Nobutaka Shimizu (Institute of Science Tokyo); Takeharu Shiraga (Chuo University)
Order Statistics in Population Protocols via Simple Dynamics
Niccolò D’Archivio (INRIA); Hind AlMahmoud (Kings College London); Emanuele Natale (CNRS, COATI, I3S, Université Côte d’Azur); Frederik Mallmann-Trenn (King’s College London)
Distributed Treewidth Computation and Courcelle’s Theorem in the CONGEST Model
Benjamín Jauregui (Universidad de Chile); Jason Li (CMU); Pedro Montealegre (Universidad Adolfo Ibáñez); Ioan Todinca (Université d’Orléans)
Early-Stabilizing Counting
Christoph Lenzen (Aalto University); Julian Loss (Ruhr University Bochum)
Information-Theoretic Optimistic Verifiable Secret Sharing
Chen-Da Liu-Zhang (Lucerne University of Applied Sciences and Arts); Martin Hirt, Emanuele Marsicano (ETH Zurich)
Distributed Algorithms for Potential Problems
Alkida Balliu, Thomas Boudier, Francesco d’Amore (Gran Sasso Science Institute); Fabian Kuhn (University of Freiburg); Dennis Olivetti (Gran Sasso Science Institute); Gustav Schmid (University of Freiburg); Jukka Suomela (Aalto University)
Byzantine Consensus in the Partially Authenticated Setting
Christoph Lenzen (Reykjavik University); Julian Loss (Ruhr University Bochum); Kecheng Shi (CISPA Helmholtz Center for Information Security); Benedikt Wagner (Ethereum Foundation)
Two Fast Array Algorithms: Reinitializable and RMWable
N. Efe Çekirge, Owen Chen, Siddhartha Jayanti, Evan Lucca (Dartmouth College)
Distributed Stochastic Graph Algorithms
Keren Censor-Hillel (Technion); Aditi Dudeja (The Chinese University of Hong Kong, Shenzhen); George Giakkoupis (Inria)
Girth Approximations in the CONGEST Model
Shiri Chechik (Tel Aviv University); Gur Lifshitz (Tel-Aviv University); Doron Mukhtar (Tel Aviv University)
New Hardness Results for the LOCAL Model via a Simple Self-Reduction
Alkida Balliu, Filippo Casagrande, Francesco d’Amore, Dennis Olivetti (Gran Sasso Science Institute)
Supervised Distributed Computing: Efficiency and Robustness under a Majority of Adversarial Workers
John Augustine (Indian Institute of Technology Madras); Henning Hillebrandt (Paderborn University); Manish Kumar (Indian Institute of Technology Madras); Christian Scheideler, Julian Werthmann (Paderborn University)
Informative Trains: A Memory-Efficient Journey to a Self-Stabilizing Leader Election Algorithm in Anonymous Graphs
Lélia Blin (IRIF, Université Paris Cité); Sylvain Gay (IRIF, Université Paris Cité, École Normale Supérieure); Isabella Ziccardi (IRIF, CNRS, Université Paris Cité)
A Separation Between Optimal Demand-Oblivious and Demand-Aware Network Throughput
Matthias Bentert (TU Berlin); Chen Avin (Ben Gurion University of the Negev); Stefan Schmid (TU Berlin)
Nearly Quadratic Asynchronous Distributed Key Generation from Recursive Consensus
Ittai Abraham (A16Z); Renas Bacho (CISPA Helmholtz Center for Information Security); Julian Loss (Ruhr University Bochum); Gilad Stern (Tel Aviv University, Israel)
Fast Gossip-based Rumor Spreading Using Small Messages
Fabien Dufoulon (Lancaster University); William K. Moses Jr. (Durham University); Gopal Pandurangan (University of Houston)
Improved Bounds for Distributed Random Walks and Spanning Trees
Gopal Pandurangan (University of Houston); Sriram V. Pemmaraju, Sourya Roy, Joshua Z. Sobel (University of Iowa)
Fast Byzantine Total Order Broadcast
Matteo Monti (HES-SO Valais-Wallis); Martina Camaioni (EPFL); Pierre-Louis Roman
The Distributed Complexity Landscape on Trees Depends on the Knowledge About the Network Size
Gustav Schmid (University of Freiburg); Alkida Balliu (Gran Sasso Science Institute); Fabian Kuhn (University of Freiburg); Dennis Olivetti (GSSI, L’Aquila, Italy); Sebastian Brandt (CISPA Helmholtz Center for Information Security); Timothe Picavet (LaBRI, Université de Bordeaux)
Why Canonical-Round Algorithms Fail for Optimal Byzantine Resilience
Hagit Attiya, Itay Flam (Technion); Jennifer Welch (TAMU)
Complementary Time-Space Tradeoff for Self-Stabilizing Leader Election: Polynomial States Meet Sublinear Time
Yuichi Sudo (Hosei University)
Simple and Efficient Randomized Wait-Free Locks
Kahbod Aeini, Dante Bencivenga (University of Calgary); George Giakkoupis (INRIA Rennes); Philipp Woelfel (University of Calgary, Canada)
Adaptively Secure Asynchronous Common Coin and Byzantine Agreement With Near-optimal Resilience and Õ(sqrt(n))-bit per Party
Hanwen Feng, Tiancheng Mai, Qiang Tang (The University of Sydney)
Conflict-Freedom as a Progress Condition
Petr Kuznetsov (Télécom Paris, Institut Polytechnique Paris); Pierre Sutra (Télécom SudParis, Institut Polytechnique de Paris); Guillermo Toyos-Marfurt (Télécom Paris, Institut Polytechnique de Paris)
Gradient Clock Synchronization with Practically Constant Local Skew
Christoph Lenzen (CISPA Helmholtz Center for Information Security)
Meta-Theorems for Cuttable Distributed Problems
Marthe Bonamy (LaBRI – CNRS, University of Bordeaux); Cyril Gavoille (LaBRI – University of Bordeaux); Avinandan Das, Jukka Suomela (Aalto University); Timothé Picavet (LaBRI – University of Bordeaux); Alexandra Wesolek (LaBRI – CNRS, University of Bordeaux)
Network-Agnostic Multidimensional Approximate Agreement with Optimal Resilience
Diana Ghinea (Lucerne University of Applied Sciences and Arts); Darya Melnyk, Tijana Milentijević (TU Berlin)
Distinct Gathering and the Virtue of Self-Consistency
Fabian Frei (MIT); Koichi Wada (Hosei U. Japan)
From Few to Many Faults: Optimal Adaptive Byzantine Agreement
Andrei Constantinescu, Marc Dufay, Anton Paramonov, Roger Wattenhofer (ETH Zurich)
Forget-IT: Optimal Good-Case Latency For Information-Theoretic BFT
Ittai Abraham (A16Z); Sourav Das (Category Labs); Yuval Efron (Ritual);
Jovan Komatovic (Category Labs)
Near-Resolution of the Tradeoff Conjecture in Distributed Proof Labeling Schemes
Arnold Filtser, Orr Fischer (Bar-Ilan University)
Round and Resilience-Optimal Approximate Agreement on Trees and Block Graphs
Marc Fuchs (University of Freiburg); Diana Ghinea (Lucerne University of Applied Sciences and Arts); Zahra Parsaeian (University of Freiburg); Joel Rybicki (Humboldt University of Berlin)
Generalized Compare-and-Swap and Space-Efficient Universal Constructions for the Infinite-Arrival Model
Vassos Hadzilacos, Myles Thiessen, Sam Toueg (University of Toronto)
Brief Announcements
Exponential Quantum Advantage for Message Complexity in Distributed Algorithms
Maël Luce (Nagoya University); Mathieu Roget (Université Aix-Marseille); Joseph Marchand (Ecole normale supérieure Paris-Saclay); François Le Gall (Nagoya University)
Is a LOCAL Algorithm Computable?
Antonio Cruciani, Avinandan Das, Massimo Equi, Henrik Lievonen (Aalto University); Diep Luong-Le (Columbia University); Augusto Modanese
(CISPA Helmholtz Center for Information Security); Jukka Suomela (Aalto University)
Amortized Asynchronous Byzantine Reliable Broadcast with Optimal Resilience
Michael Yiqing Hu, Hong Yao Alvin Yan, Jialin Li (National University of Singapore)
Delay-Optimal Transaction Order Fairness
Zhuo Cai (Hong Kong University of Science and Technology); Amir K. Goharshady (University of Oxford)
Byzantine Machine Learning, MultiKrum and an Optimal Notion of Robustness
Gilles Bareilles (École Polytechnique); Wassim Bouaziz (Mistral AI); Julien Fageot (EPFL); El-Mahdi El-Mhamdi (École Polytechnique)
Communication Efficient Byzantine Agreement with Predictions
Muhammad Ayaz Dzulfikar, Seth Gilbert (National University of Singapore)
Cryptographically Secure Domain Extension for Byzantine Agreement with Improved Round Complexity
Ashish Choudhury, Madhav Natarajan H (IIIT Bangalore)
It Does Not Matter How You Define Locally Checkable Labelings
Antonio Cruciani, Avinandan Das, Alesya Raevskaya, Jukka Suomela (Aalto University)
DéjàVu: A Minimalistic Mechanism for Distributed Plurality Consensus
Francesco d’Amore (Gran Sasso Science Institute); Niccolò D’Archivio (Inria); George Giakkoupis (Inria Rennes); Frédéric Giroire (CNRS/
Université Côte d’Azur); Emanuele Natale (CNRS, COATI, I3S, Université Côte d’Azur)
Computing Least Fixed Points with Overwrite Semantics in Parallel and Distributed Systems
Vijay K. Garg (The University of Texas at Austin); Rohan Garg (Purdue University)
What Is Agreement About if Not Common Knowledge?
Or David, Yoram Moses (Technion)
Distributed Statistical Zero-Knowledge Proofs via Sumcheck
Benjamín Jauregui (Universidad de Chile & Université Paris Cité); Masayuki Miyamoto (University of Tsukuba)
A Space-Efficient Lock-Free Linear-Probing Hash Table
Hagit Attiya (Technion); Rotem Oshman (Tel Aviv University and NYU); Noa Schiller (Tel Aviv University)
2-Coloring Cycles in One Round
Maxime Flin, Alesya Raevskaya, Ronja Stimpert, Jukka Suomela, Qingxin Yang (Aalto University)
On Energy Complexity and Multi-Instance Computation in the Congested Clique
Dominick Banasik, Varsha Dani (Rochester Institute of Technology)
Toward Uniform Content-Oblivious Leader Election on General Graphs
Fabian Frei (MIT); Ran Gelles (Bar-Ilan University); Ahmed Ghazy (CISPA Helmholtz Center for Information Security); Alexandre Nolin (Télécom SudParis)
Deterministic Edge Coloring with few Colors in CONGEST
Tijn de Vos, Yannic Maus (TU Graz); Joakim Blikstad (Centrum Wiskunde & Informatica (CWI))
Sinkless Orientation Made Trivial
Alexandre Nolin (Télécom SudParis)
Fast Deterministic Distributed Degree Splitting
Yannic Maus (TU Graz); Alexandre Nolin (Télécom SudParis); Florian Schager (TU Graz)
Subcubic Coin Tossing in Asynchrony without Setup
Mose Mizrahi, Roger Wattenhofer (ETH Zurich)
Limit Laws for Consensus Protocols on the Complete Graph
Julian Becker, Konstantinos Panagiotou (LMU Munich)
Distributed Non-Interactive Zero-Knowledge Proofs
Alex Bredariol Grilo (CNRS, Sorbonne Université); Ami Paz (LISN, CNRS, Paris-Saclay University); Mor Perry (The Academic College of Tel-Aviv-Yaffo)
BumbleBee: Best-of-Both-Worlds MVBA with Optimal Communication, Latency and Resilience Tradeoffs
Fatima Elsheimy (Yale University); Simon Kamp (Ruhr University Bochum)