Conference Program

Sunday 7/23 12:00-1:00PM
Sunday 7/23 1:00-1:45PM
Keynote Taking Concurrency Seriously: New Directions in Multiprocessor Synchronization
Maurice Herlihy
Break 1:45-2:00PM
Retro-RUMP Session 2:00-3:15PM
Coffee break 3:15-3:45PM
Sunday 7/23 3:45-4:30PM
Keynote Century papers at the First Quarter-Century Milestone
Danny Dolev
Break 4:30-4:45PM
Sunday 7/23 4:45-5:30PM
Keynote Paxos Made Live - An Engineering Perspective
Tushar Chandra
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 8:00-9:00AM
Continental Breakfast
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
Session chair: Kunar Talwar
  • 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
Session chair: Haifeng Yu
  • 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
Session chair: Jared Saia
  • 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 8:00-9:00AM
Continental Breakfast
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
Session chair: Cyril Gavoille
  • 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
Session chair: Eric Ruppert
  • 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
Session chair: Fabian Kuhn
  • 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 8:00-9:00AM
Continental Breakfast
Wednesday 7/26 9:00-10:30AM
Session Shared Memory
Session chair: Tim Harris
  • 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
Session chair: Michael Merritt
  • 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
Session chair: Boaz Patt-Shamir
  • 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
Session chair: Jennifer Welch
  • 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