Outstanding Papers


Best Paper
Michael Dinitz, Jeremy Fineman, Seth Gilbert and Calvin Newport “Smoothed Analysis of Information Spreading in Dynamic Networks”
Best Student Paper
Gal Amram, Avi Hayoun, Lior Mizrahi and Gera Weiss “Polynomial-Time Verification and Testing of Implementations of the Snapshot Data Structure”
Pierre Civit, Muhammad Ayaz Dzulfikar, Seth Gilbert, Vincent Gramoli, Rachid Guerraoui, Jovan Komatovic and Manuel Vidigueira “Byzantine Consensus Is Θ(n^2): The Dolev-Reischuk Bound Is Tight Even in Partial Synchrony!”


Best Paper
Dan Alistarh, Giorgi Nadiradze and Rati Gelashvili “Lower Bounds for Shared-Memory Leader Election under Bounded Write Contention”
Best Student Paper
Yael Hitron and Merav Parter “Broadcast CONGEST Algorithms against Adversarial Edges”
Yael Hitron and Merav Parter “General CONGEST Compilers against Adversarial Edges”


Best Paper
Sepehr Assadi, Aaron Bernstein and Zachary Langley “Improved Bounds for Distributed Load Balancing”
Best Student Paper
Arik Rinberg and Idit Keidar “Intermediate Value Linearizability: A Quantitative Correctness Criterion”


Best Paper
Orr Fischer and Rotem Oshman: “A Distributed Algorithm for Directed Minimum-Weight
Spanning Tree”
Rachid Guerraoui, Petr Kuznetsov, Matteo Monti, Matej Pavlovic and Dragos-Adrian
Seredinschi: “Scalable Byzantine Reliable Broadcast”


Best Paper
Gregory Chockler and Alexey Gotsman “Multi-Shot Distributed Transaction Commit”
Ali Mashreghi and Valerie King “Broadcast and minimum spanning tree with o(m) messages in the asynchronous CONGEST model”


Best Paper
Mohsen Ghaffari, Juho Hirvonen, Fabian Kuhn, Yannic Maus, Jukka Suomela and Jara Uitto “Improved Distributed Degree Splitting and Edge Coloring”
Best Student Paper
Manuela Fischer “Improved Deterministic Distributed Matching via Rounding”


Best Paper
Dan Hefetz, Fabian Kuhn, Yannic Maus and Angelika Steger “Polynomial Lower Bound for Distributed Graph Coloring in a Weak LOCAL Model”
Best Student Paper Candidates
Amir Abboud, Keren Censor-Hillel and Seri Khoury “Near-Linear Lower Bounds for Distributed Distance Computations, Even in Sparse Networks”
Hagit Attiya, Ohad Ben-Baruch and Danny Hendler “Lower Bound on the Step Complexity of Anonymous Binary Consensus”
Lili Su and Nitin H. Vaidya “Non-Bayesian Learning in the Presence of Byzantine Agents”


Best Paper
Rati Gelashvili “On the Optimal Space Complexity of Consensus for Anonymous Processes”
Best Student Paper
Yuezhou Lv “Local Information in Influence Networks”


Best Paper
Ho-Lin Chen, Rachel Cummings, David Doty and David Soloveichik “Speed Faults in Computation by Chemical Reaction Networks”
Best Student Paper
Merav Parter “Vertex Fault Tolerant Additive Spanners”


Best Paper
Mohsen Ghaffari and Fabian Kuhn “Distributed Minimum Cut Approximation”
Best Student Paper
Shahar Timnat and Erez Petrank “Lock-Free Iterators”


Best Paper
Mika Goos and Jukka Suomela “No Sublogarithmic-Time Approximation Scheme for Bipartite Vertex Cover”
Best Student Paper
Yehuda Afek, Haim Kaplan, Boris Korenfeld, Adam Morisson and Robert E. Tarjan “CBTree: A Practical Concurrent Self-Adjusting Search Tree”


Best Paper
Pierre Fraigniaud , Sergio Rajsbaum and Corentin Travers “Locality and Checkability in Wait-free Computing”
Best Student Paper
Yehuda Afek , Michael Hakimi and Adam Morrison “Fast and Scalable Rendezvousing”


Best Student Paper
François Bonnet and Michel Raynal “Anonymous Asynchronous Systems: the Case of Failure Detectors”


Best Paper
Carole Delporte-Gallet , Hugues Fauconnier , Rachid Guerraoui and Andreas Tielmann “The Disagreement Power of an Adversary”
Best Student Paper
Henrique Moniz , Nuno Ferreira Neves , Miguel Correia and Paulo Veríssimo “Randomization Can Be a Healer: Consensus with Dynamic Omission Failures”


Best Paper
Robert Danek and Wojciech Golab “Closing the Complexity Gap between FCFS Mutual Exclusion and Mutual Exclusion”
Best Student Paper
Andrzej Czygrinow , Michal Hanckowiak and Wojciech Wawrzyniak “Fast distributed approximations in planar graphs”


Best Student Paper
Dana Angluin , James Aspnes and David Eisenstat “A Simple Population Protocol for Fast Robust Approximate Majority”
Special Issue of Distributed Computing
Dana Angluin , James Aspnes and David Eisenstat : “A Simple Population Protocol for Fast Robust Approximate Majority”
Faith Ellen , Panagiota Fatourou and Eric Ruppert : “The Space Complexity of Unbounded Timestamps”
Leszek Gasieniec , Erez Kantor , Dariusz R. Kowalski , David Peleg and Chang Su : “Time efficient k-shot broadcasting in known topology radio networks”
Simon Fischer , Lars Olbrich and Berthold Vöcking : “Approximating Wardrop Equilibria with Finitely Many Agents”
Amos Korman and David Peleg : “Compact Separator Decompositions in Dynamic Trees and Applications to Labeling Schemes”


Best Student Paper
Maleq Khan and Gopal Pandurangan “A Fast Distributed Approximation Algorithm for Minimum Spanning Trees”
Special Issue of Distributed Computing
Maleq Khan and Gopal Pandurangan : “A Fast Distributed Approximation Algorithm for Minimum Spanning Trees”
Piotr Zielinski : “Low-latency Atomic Broadcast in the presence of contention”
Michael Okun , Amnon Barak and Eli Gafni : “Renaming in Message Passing Systems with Byzantine Failures”
Rachid Guerraoui , Michal Kapalka and Petr Kouznetsov : “The Weakest Failure Detectors to Boost Obstruction-Freedom”


Best Student Paper
Korman, A. “General Compact Labeling Schemes for Dynamic Trees”
Special Issue of Distributed Computing
Rachid Guerraoui and Eric Ruppert : “Anonymous and fault-tolerant shared-memory computing”
Amos Korman : “General compact labeling schemes for dynamic trees”
Maurice Herlihy and Ye Sun : “Distributed transactional memory for metric-space networks”
Dahlia Malkhi and Doug Terry : “Concise version vectors in WinFS”
Yehuda Afek and Yaron De Levie : “Efficient adaptive collect algorithms”


Best Student Paper
Hagit Attiya , Fabian Kuhn , Mirjam Wattenhofer and Roger Wattenhofer “Efficient Adaptive Collect using Randomization”
Laurent Fribourg , Stephane Messika and Claudine Picaronny “Coupling and Self-Stabilization”
Special Issue of Distributed Computing
Harry Buhrman , Alessandro Panconesi , Riccardo Silvestri and Paul Vitanyi : “On the importance of having an identity or, is consensus really universal?”
Hagit Attiya , Fabian Kuhn , C. Greg Plaxton , Mirjam Wattenhofer and Roger Wattenhofer : “Efficient adaptive collect using randomization”
Danny Hendler , Yossi Lev , Mark Moir and Nir Shavit : “A dynamic-sized nonblocking work stealing deque”
James Aspnes , Faith Ellen Fich and Eric Ruppert : “Relationships between broadcast and shared memory in reliable anonymous distributed systems”
Laurent Fribourg , Stéphane Messika and laudine Picaronny : “Coupling and self-stabilization”


Best Student Paper
Ittai Abraham and Dahlia Malkhi ” Probabilistic Quorums for Dynamic Systems”
Special Issue of Distributed Computing
Noga Alon , Michael Merritt , Omer Reingold , Gadi Taubenfeld and Rebecca N. Wright : “Tight bounds for shared memory systems accessed by Byzantine processes”
Ittai Abraham and Dahlia Malkhi : “Probabilistic quorums for dynamic systems”
Shlomi Dolev , Seth Gilbert , Nancy A. Lynch , Alexander A. Shvartsman and Jennifer L. Welch : “GeoQuorums: implementing atomic memory in mobile ad hoc networks”
M. Herlihy and L. D. Penso : “Tight bounds for k-set agreement with limited-scope failure detectors”


Best Student Paper
Yongqiang Huang and Hector Garcia-Molina “Assignment-based Partitioning in a Condition Monitoring System”


Best Student Paper
Yong-Jik Kim and James H. Anderson “A Time Complexity Bound for Adaptive Mutual Exclusion”


Best Student Paper
Hagit Attiya and Arie Fouren “Polynominal and Adaptive Long-Lived (2-1)-Renaming”


Best Student Paper
Marcos Kawazoe Aguilera , Sam Toueg and Borislav Deianov “Revising the Weakest Failure Detector for Uniform Reliable Broadcast”


Best Student Paper
Michael J. Demmer and Maurice Herlihy “The Arrow Distributed Directory Protocol”