List of accepted papers

Full Papers

The Complexity of Distributed Approximation of Packing and Covering Integer Linear Programs
Yi-Jun Chang and Zeyong Li

Asynchronous Wait-Free Runtime Verification and Enforcement of Linearizability
Armando Castañeda and Valeria Rodríguez-Jiménez

The ERA Theorem for Safe Memory Reclamation
Gali Sheffi and Erez Petrank

A Wait-free Queue with Polylogarithmic Step Complexity
Hossein Naderibeni and Eric Ruppert

On the Validity of Consensus
Pierre Civit, Seth Gilbert, Rachid Guerraoui, Jovan Komatovic and Manuel Vidigueira

(1-ε)-Approximate Maximum Weighted Matching in poly(1/ε, log n) Time in the Distributed and Parallel Settings
Shang-En Huang and Hsin-Hao Su

BeeGees: strengthened liveness in chained BFT
Ittai Abraham, Natacha Crooks, Neil Giridharan, Heidi Howard and Florian Suri-Payer

Optimal Eventual Byzantine Agreement Protocols with Omission Failures
Kaya Alpturer, Joseph Halpern and Ron van der Meyden

Distributed MIS in O(log log n) Awake Complexity
Fabien Dufoulon, William K. Moses Jr. and Gopal Pandurangan

Improved Tradeoffs for Leader Election
Shay Kutten, Peter Robinson, Ming Ming Tan and Xianbin Zhu

Distributed CONGEST Algorithms against Mobile Adversaries
Orr Fischer and Merav Parter

Distributed Symmetry Breaking on Power Graphs via Sparsification
Yannic Maus, Jara Uitto and Saku Peltonen

Distributed Self-Stabilizing MIS with Few States and Weak Communication
George Giakkoupis and Isabella Ziccardi

Deterministic Fault-Tolerant Connectivity Labeling Scheme
Taisuke Izumi, Yuval Emek, Tadashi Wadayama and Toshimitsu Masuzawa

Sparse Semi-Oblivious Routing: Few Random Paths Suffice
Goran Zuzic, Bernhard Haeupler and Antti Roeyskoe

A Near Time-optimal Population Protocol for Self-stabilizing Leader Election on Rings with a Poly-logarithmic Number of States
Daisuke Yokota, Yuichi Sudo, Toshimitsu Masuzawa and Fukuhito Ooshita

Distributed MIS with Low Energy and Time Complexities
Mohsen Ghaffari and Julian Portmann

The Impact of Cooperation in Bilateral Network Creation
Tobias Friedrich, Hans Gawendowicz, Pascal Lenzner and Arthur Zahn

Fast Convergence of k-Opinion Undecided State Dynamics in the Population Protocol Model
Talley Amir, James Aspnes, Petra Berenbrink, Felix Biermeier, Christopher Hahn, Dominik Kaaser and John Lazarsfeld

Universally Composable Simultaneous Broadcast against a Dishonest Majority and Applications
Myrto Arapinis, Ábel Kocsis, Nikolaos Lamprou, Liam Medley and Thomas Zacharias

Distributed Averaging in Opinion Dynamics
Petra Berenbrink, Colin Cooper, Cristina Gava, David Kohan Marzagão, Frederik Mallmann-Trenn, Tomasz Radzik and Nicolas Rivera

Optimal Message-Passing with Noisy Beeps
Peter Davies

Uniting General-Graph and Geometric-Based Radio Networks via Independence Number Parametrization
Peter Davies

On the Amortized Communication Complexity of Byzantine Broadcast
Atsuki Momose, Ling Ren, Elaine Shi, Jun Wan and Zhuolun Xiang

Word-Size RMR Trade-offs for Recoverable Mutual Exclusion
David Yu Cheng Chan, George Giakkoupis and Philipp Woelfel

A Near-Optimal Deterministic Distributed Synchronizer
Mohsen Ghaffari and Anton Trygub

Deterministic Fault-Tolerant Distributed Computing in Linear Time and Communication
Jan Olkowski, Bogdan Chlebus and Dariusz Kowalski

Efficient Bounded Timestamping from Standard Synchronization Primitives
Benyamin Bashari, Ali Jamadi and Philipp Woelfel

Efficient Distributed Decomposition and Routing Algorithms in Minor-free Networks and their Applications
Yi-Jun Chang

Brief announcements

Brief Announcement: Near-Optimal Compact Routing and Decomposition Schemes for Planar Graphs
Jinfeng Dou, Thorsten Götte, Henning Hillebrandt, Christian Scheideler and Julian Werthmann

Brief Announcement: Minimum Cost Maximum Flow in the CONGEST Model
Tijn de Vos

Brief Announcement: Breadth-First Depth-Next: Optimal Collaborative Exploration of Trees with Low Diameter
Romain Cosson, Laurent Massoulie and Laurent Viennot

Brief Announcement: Send/Receive Patterns versus Read/Write Patterns: the MB-Broadcast Abstraction
Mathilde Déprés, Achour Mostéfaoui, Matthieu Perrin and Michel Raynal

Brief Announcement: Breaking through the Ω(n)-space barrier: Population Protocols Decide Double-exponential Thresholds
Philipp Czerner

Brief Announcement: What Can We Compute in a Single Round of the Congested Clique?
Peter Robinson

Brief Announcement: The Laplacian Paradigm in Deterministic Congested Clique
Tijn de Vos and Sebastian Forster

Brief Announcement: Breaking the f+1 Barrier: Executing Payment Transactions in Parallel with Less than f+1 Validations
Rida Bazzi and Sara Tucci-Piergiovanni

Brief Announcement: Discrete Incremental Voting
Colin Cooper, Tomasz Radzik and Takeharu Shiraga

Brief Announcement: Local Problems in the SUPPORTED Model
Akanksha Agrawal, John Augustine, David Peleg and Srikkanth Ramachandran

Brief Announcement: Efficient Computation in Congested Anonymous Dynamic Networks
Giovanni Viglietta and Giuseppe Antonio Di Luna

Brief Announcement: Durable Algorithms for Writable LL/SC and CAS with Dynamic Joining
Prasad Jayanti, Siddhartha Visveswara Jayanti and Sucharita Jayanti

Brief Announcement: Improved Consensus in Quantum Networks
Jan Olkowski, Dariusz Kowalski and MohammadTaghi Hajiaghayi

Brief Announcement: Improved, Partially-Tight Multiplicity Queue Lower Bounds
Anh Tran and Edward Talmage

Brief Announcement: CausalEC: A Causally Consistent Data Storage Algorithm based on Cross-Object Erasure Coding
Viveck Cadambe and Shihang Lyu