Preliminary Program

Sunday 7/23 1:00-3:00PM
Keynote Taking Concurrency Seriously:
New Directions in Multiprocessor Synchronization
Maurice Herlihy
Keynote Century papers at the First Quarter-Century Milestone
Danny Dolev
Coffee break 3:00-3:30PM
Keynote TBA
Tushar Chandra
Retro-RUMP Session TBA
Reception and Poster Session 5:30-7:30PM
  • Content Availability and Signaling Overhead in DHT Systems for Mobile Environments
    Stefan Zoels, Simon Schubert, Wolfgang Kellerer, Zoran Despotovic
  • An Optimal Distributed Bridge-Finding Algorithm
    David Pritchard
  • Dynamic Medial Axis Based Motion Planning in Sensor Networks
    Lan Lin, Hyunyoung Lee
  • Implementing a Reliable Local Broadcast Primitive in Wireless Ad Hoc Networks
    Vartika Bhandari, Nitin H. Vaidya
  • On Efficient Departure for Dynamic Asynchronous Systems
    Sathya Peri, Neeraj Mittal
Monday 7/24 9:00-10:00AM
Keynote Distributed Social Systems
Jon Kleinberg
Coffee break 10:00-10:30AM
Monday 7/24 10:30AM-12:00PM
Session Graph Algorithms
On the Complexity of Distributed Graph Coloring
Fabian Kuhn, Roger Wattenhofer
Quorum Placement in Networks: Minimizing Network Congestion
Daniel Golovin, Anupam Gupta, Bruce Maggs, Florian Oprea, Michael Reiter
Distributed Verification of Minimum Spanning Trees
Amos Korman, Shay Kutten
Lunch 12:00-1:00PM
Monday 7/24 1:00-3:00PM
Session Game Theory
When Selfish Meets Evil: Byzantine Players in a Virus Inoculation Game
Thomas Moscibroda, Stefan Schmid, Roger Wattenhofer
Routing Without Regret: On Convergence to Nash Equilibria of Regret-Minimizing Algorithms in Routing Games
Avrim Blum, Eyal Even-Dar, Katrina Ligett
Distributed Computing Meets Game Theory: Robust Mechanisms for Rational Secret Sharing and Multiparty Computation
Ittai Abraham, Danny Dolev, Rica Gonen, Joseph Halpern
EquiCast: Scalable Multicast with Selfish Users
Idit Keidar, Roie Melamed, Ariel Orda
Coffee break 3:00-3:30PM
Monday 7/24 3:30-5:30PM
Session Algorithms
Grouped Distributed Queues: Distributed Queue, Proportional Share Multiprocessor Scheduling
Bogdan Caprita, Jason Nieh, Clifford Stein
Sketching Asynchronous Streams Over Sliding Windows
Srikanta Tirthapura, Bojian Xu, Costas Busch
Adversarial queuing on the multiple-access channel
Bogdan Chlebus, Dariusz Kowalski, Mariusz Rokicki
Veracity Radius - Capturing the Locality of Distributed Computrations
Yitzhak Birk, Idit Keidar, Liran Liss, Assaf Schuster, Ran Wolff
Business meeting 8:00-10:00PM
Tuesday 7/25 9:00-10:00AM
Keynote Life is not a State-Machine;
The Long Road from Research to Production
Werner Vogels
Coffee break 10:00-10:30AM
Tuesday 7/25 10:30AM-12:00PM
Session Peer-to-peer
Computing Separable Functions via Gossip
Damon Mosk-Aoyama, Devavrat Shah
Peer Counting and Sampling in overlay networks: random walk methods
Laurent Massoulie, Erwan Le Merrer, Anne-Marie Kermarrec, Ayalvadi Ganesh
On the Topologies Formed by Selfish Peers
Thomas Moscibroda, Stefan Schmid, Roger Wattenhofer
(on your own)
Tuesday 7/25 1:30-3:30PM
Session Agreement Problems
Self-stabilizing Byzantine Agreement
Ariel Daliot, Danny Dolev
Irreducibility and Additivity of Set Agreement-oriented Failure Detector Classes
Corentin Travers, Achour Mostefaoui, Sergio Rajsbaum, Michel Raynal
Optimally Efficient Multi-Valued Byzantine Agreement
Matthias Fitzi, Martin Hirt
Timeliness, Failure-Detectors, and Consensus Performance
Idit Keidar, Alexander Shraer
Coffee break 3:30-4:00PM
Tuesday 7/25 4:00-6:00PM
Session Graph Algorithms
Oracle size: a new measure of difficulty for communication tasks
Pierre Fraigniraud, David Ilcinkas, Andrzej Pelc
Object Location Using Path Separators
Ittai Abraham, Cyril Gavoille
On Optimal Stretch Name-Independent Compact Routing in Doubling Metrics
Donglin Xia, Goran Konjevod, Andréa Richa
Local Approximation Schemes for Topology Control
Mirela Damian, Saurav Pandit, Sriram Pemmaraju
Banquet and Award Ceremony 7:00-10:00PM
Wednesday 7/26 9:00-10:30AM
Session Shared Memory
Common2 extended to stacks and unbounded concurrency
Yehuda Afek, Eli Gafni, Adam Morrison
Single-Scanner Multi-Writer Snapshot Implementations are Fast!
Panagiota Fatourou, Nikolaos Kallimanis
An O(1) RMRs Leader Election Algorithm
Wojciech Golab, Danny Hendler, Philipp Woelfel
Coffee break 10:30-11:00AM
Wednesday 7/26 11:00AM-12:30PM
Session Fault Tolerance
How fast can a very robust read be?
Rachid Guerraoui, Marko Vukolic
Reliable Broadcast in Radio Networks: The Bounded Collision Case
Chiu-Yuen Koo, Vartika Bhandari, Jonathan Katz, Nitin H. Vaidya
(Im)Possibility and Complexity of Probabilistic Reliable Communication in Directed Networks
Kannan Srinathan, C. Pandu Rangan
Lunch 12:30-1:30PM
Wednesday 7/26 1:30-3:00PM
Session Algorithms and Lower Bounds
An Ω(n log n) Lower Bound on the Cost of Mutual Exclusion
Rui Fan, Nancy Lynch
A Lower Bound for Scalable Byzantine Agreement
Dan Holtby, Bruce Kapron, Valerie King
Stably Computable Predicates are Semilinear
Dana Angluin, James Aspnes, David Eisenstat
Coffee break 3:00-3:30PM
Wednesday 7/26 3:30-4:30PM
Session Shared Memory Synchronization

Synchronizing without Locks is Inherently Expensive
Hagit Attiya, Rachid Guerraoui, Danny Hendler, Petr Kouznetsov

Transactional Contention Management as a Non-Clairvoyant Scheduling Problem
Hagit Attiya, Leah Epstein, Hadas Shachnai, Tami Tamir