2023
Best Paper
Pierre Civit, Seth Gilbert, Rachid Guerraoui, Jovan Komatovic, Matteo Monti and Manuel Vidigueira “Every Bit Counts in Consensus”
Alkida Balliu, Sebastian Brandt, Fabian Kuhn, Dennis Olivetti and Gustav Schmid “On the Node-Averaged Complexity of Locally Checkable Problems on Trees”
Best Student Paper
Naama Ben-David, Gal Sela and Adriana Szekeres “The FIDS Theorems: Tensions between Multinode and Multicore Performance in Transactional Systems”
2022
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!”
2021
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”
2020
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”
2019
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”
2018
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”
2017
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”
2016
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”
2015
Best Paper
Rati Gelashvili “On the Optimal Space Complexity of Consensus for Anonymous Processes”
Best Student Paper
Yuezhou Lv “Local Information in Influence Networks”
2014
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”
2013
Best Paper
Mohsen Ghaffari and Fabian Kuhn “Distributed Minimum Cut Approximation”
Best Student Paper
Shahar Timnat and Erez Petrank “Lock-Free Iterators”
2012
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”
2011
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”
2010
Best Student Paper
François Bonnet and Michel Raynal “Anonymous Asynchronous Systems: the Case of Failure Detectors”
2009
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”
2008
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”
2007
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”
2006
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”
2005
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”
2004
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”
2003
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”
2002
Best Student Paper
Yongqiang Huang and Hector Garcia-Molina “Assignment-based Partitioning in a Condition Monitoring System”
2001
Best Student Paper
Yong-Jik Kim and James H. Anderson “A Time Complexity Bound for Adaptive Mutual Exclusion”
2000
Best Student Paper
Hagit Attiya and Arie Fouren “Polynominal and Adaptive Long-Lived (2-1)-Renaming”
1999
Best Student Paper
Marcos Kawazoe Aguilera , Sam Toueg and Borislav Deianov “Revising the Weakest Failure Detector for Uniform Reliable Broadcast”
1998
Best Student Paper
Michael J. Demmer and Maurice Herlihy “The Arrow Distributed Directory Protocol”