International Symposium on DIStributed Computing (DISC)

Outstanding Papers


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”