Conference Program
|
Sunday 7/23 |
12:00-1:00PM |
|
|
Registration |
|
Sunday 7/23 |
1:00-1:45PM |
|
Keynote |
Taking Concurrency Seriously:
|
|
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 MilestoneDanny Dolev |
|
Break |
4:30-4:45PM |
|
Sunday 7/23 |
4:45-5:30PM |
|
Keynote |
Paxos Made Live - An Engineering PerspectiveTushar Chandra |
|
Reception and Poster Session |
5:30-7:30PM
|
|
|
|
|
Monday 7/24 |
8:00-9:00AM |
|
|
Continental Breakfast |
|
Monday 7/24 |
9:00-10:00AM |
|
Keynote |
Distributed Social SystemsJon 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;
|
|
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 |
|
Lunch |
12:00-1:30PM |
|
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 |