Microsoft Research
Oracle Labs


Download the scheduled program as pdf.

Regular papers

Dan Alistarh, James Aspnes, George Giakkoupis, and Philipp Woelfel
Sub-logarithmic Randomized Loose Renaming

Vassos Hadzilacos and Sam Toueg
On Deterministic Abortable Objects

Edmund Wong and Lorenzo Alvisi
What’s a Little Collusion Between Friends?

Nicolas Braud-Santoni, Rachid Guerraoui, and Florian Huc
Fast Byzantine Agreement

Yuval Emek and Roger Wattenhofer
Stone Age Distributed Computing

Yoann Dieudonne, Andrzej Pelc, and Vincent Villain
How to Meet Asynchronously at Polynomial Cost

Swan Dubois and Rachid Guerraoui
Introducing Speculation in Self-Stabilization – An Application to Mutual Exclusion

Alex Scott, Peter Jeavons, and Lei Xu
Feedback from nature: an optimal distributed algorithm for maximal independent set selection

Mohsen Ghaffari, Bernhard Haeupler, and Majid Khabbazian
Broadcast in Radio Networks with Collision Detection

Michel Raynal and Julien Stainer
Round-based Synchrony Weakened by Message Adversaries vs Asynchrony Enriched with Failure Detectors

Allison Lewko and Mark Lewko
On the Complexity of Asynchronous Agreement Against Powerful Adversaries

Hagit Attiya, Armando Castaneda, Maurice Herlihy, and Ami Paz
Upper Bound on the Complexity of Solving Hard Renaming

Yuezhou Lv and Thomas Moscibroda
Fair and Resilient Incentive Tree Mechanisms

Gang Xu, George Amariucai, and Yong Guan
Delegation of Computation with Verification Outsourcing: Curious Verifiers

Hillel Avni, Nir Shavit, and Adi Suissa
Leaplist: Lessons Learned in Designing TM-Supported Range Queries

Hagit Attiya, Danny Hendler, and Smadar Levy
An O(1)-Barriers Optimal RMRs Mutual Exclusion Algorithm

Nitin Vaidya and Vijay Garg
Byzantine Vector Consensus in Complete Graphs

Sebastian Daum, Mohsen Ghaffari, Seth Gilbert, Fabian Kuhn, and Calvin

Maximal Independent Sets in Multichannel Radio Networks

Mohsen Eftekhari, Evangelos Kranakis, Danny Krizanc, Oscar Morales-Ponce,
Lata Narayanan, Jaroslav Opatrny, and Sunil Shende

Distributed Local Algorithms for Barrier Coverage using Relocatable Sensors

Mohsen Ghaffari, Nancy Lynch, and Calvin Newport
The Cost of Radio Network Broadcast for Different Models of Unreliable Links

Ralf Klasing, Adrian Kosowski, Dominik Pajak, and Thomas Sauerwald
The Multi-Agent Rotor-Router on the Ring: A Deterministic Alternative to Parallel Random Walks

Oksana Denysyuk and Luis Rodrigues
Byzantine Renaming in Synchronous Systems with t < N

Christoph Lenzen and David Peleg
Efficient Distributed Source Detection with Limited Bandwidth

Rachid Guerraoui, Florian Huc, and Anne-Marie Kermarrec
Highly Dynamic Distributed Computing with Byzantine Failures

Pierre Fraigniaud, Mika Göös, Amos Korman, and Jukka Suomela
What can be decided locally without identifiers?

Marijke Bodlaender, Magnus M. Halldorsson, and Pradipta Mitra
Connectivity and Aggregation in Multihop Wireless Networks

Chrysovalandis Agathangelou, Chryssis Georgiou, and Marios

A Distributed Algorithm for Gathering Many Fat Mobile Robots in the Plane

Hagit Attiya, Alexey Gotsman, Sandeep Hans, and Noam Rinetzky
A Programming Language Perspective on Transactional Memory Consistency

Shiri Chechik
Compact Routing Schemes with Improved Stretch

Christoph Lenzen and Danny Dolev
Early-Deciding Consensus is Expensive

Rotem Oshman and Nir Shavit
The SkipTrie: Low-Depth Concurrent Search without Rebalancing

Dariusz Kowalski and Achour Mostefaoui
Synchronous Byzantine Agreement with Nearly a Cubic Number of
Communication Bits

Ji Zhu, Stratis Ioannidis, Nidhi Hegde, and Laurent Massoulie
Stable and Scalable Universal Swarms

Trevor Brown, Faith Ellen, and Eric Ruppert
Pragmatic Primitives for Non-blocking Data Structures

Shay Kutten, Gopal Pandurangan, David Peleg, Peter Robinson, and Amitabh

On the Complexity of Universal Leader Election

John Augustine, Gopal Pandurangan, and Peter Robinson
Fast Byzantine Agreement in Dynamic Networks

Christoph Lenzen
Optimal Deterministic Routing, and Sorting on the Congested Clique

Brief Announcements:

Rachit Agarwal and Brighten Godfrey
A Simple Stretch 2 Distance Oracle

Seda Davtyan, Kishori Konwar, and Alexander Shvartsman
Self-Stabilizing Resource Discovery Algorithm

Michael Gorelik and Danny Hendler
An Asymmetric Flat-Combining Based Queue Algorithm

Armando Castaneda, Yannai A. Gonczarowski, and Yoram Moses
Pareto Optimal Solutions to Consensus and Set Consensus

Wojciech Wawrzyniak
A local constant-factor approximation algorithm for MDS problem in anonymous network

Chen Chen, Roman Vitenberg, and Hans-Arno Jacobsen
Constructing Fault-Tolerant Overlay Networks for Topic-based Publish/Subscribe

Martin Hoefer and Thomas Sauerwald
Threshold Load Balancing in Networks

Calvin Newport
A Shorter and Stronger Proof of an $Omega(Dlog{(n/D)})$ Lower Bound for Broadcast in Radio Networks

Annu John, Igor Konnov, Ulrich Schmid, Helmut Veith, and Josef Widder
Parameterized Model Checking of Fault-tolerant Distributed Algorithms by Abstraction

Zahra Aghazadeh, Wojciech Golab, and Philipp Woelfel
Resettable Objects and Efficient Memory Reclamation for Concurrent Algorithms

Lu Zhang, Xueyan Tang, and Bingsheng He
On Minimum Interaction Time for Continuous Distributed Interactive Computing

Valerie King and Jared Saia
Byzantine Agreement with a Strong Adversary in Polynomial Expected Time

Lelia Blin and Sebastien Tixeuil
Deterministic Self-Stabilizing Leader Election with O(log log n)-bits

Josh Karlin, Joud Khoury, Jared Saia, and Mahdi Zamani
Freedom not Fear: Scalable Anonymous Communication with Byzantine Adversary

Jeremy Fineman, Calvin Newport, and Tonghe Wang
Fair Maximal Independent Sets in Trees

Raissa D’Souza and Samuel Johnson
Brokerage and Closure in A Strategic Model of Social Capital

Sam Whitlock, Scott Shenker, and Colin Scott
Techniques for Programmatically Troubleshooting Distributed Systems