| Sunday 7/23 |
12:00-1:00PM |
|
Registration |
| 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 |
|
- Unreliable failure detectors for asynchronous systems,
Tushar Deepak Chandra and Sam Toueg, PODC 1991.
Presenter: Petr Kouznetsov
- Another advantage of free choice (Extended Abstract): Completely asynchronous agreement protocols,
Michael Ben-Or, PODC 1983.
Presenter: Jared Saia
- The slide mechanism with applications in dynamic networks,
Yehuda Afek, Eli Gafni, and Adi Rosen, PODC 1992.
Presenter: Yehuda Afek
- Fast network decomposition,
Baruch Awerbuch, Bonnie Berger, Lenore Cowen, and David Peleg, PODC 1992.
Presenter: David Pritchard
- Knowledge and common knowledge in a distributed environment,
Joseph Y. Halpern and Yoram Moses, PODC 1984.
Presenter: Eli Gafni
- Consensus in the Presence of Partial Synchrony (Preliminary Version),
Cynthia Dwork, Nancy A. Lynch, and Larry J. Stockmeyer, PODC 1984.
Presenter: Alexander Shraer
- Byzantine clock synchronization,
Leslie Lamport and P. M. Melliar-Smith, PODC 1984.
Presenter: Jennifer Welch
- Impossibility and universality results for wait-free synchronization,
Maurice P. Herlihy, PODC 1988.
Presenter: Prasad Jayanti
- Software transactional memory,
Nir Shavit and Dan Touitou, PODC 1995.
Presenter: Tim Harris |
| 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
|
Lunch
(on your own) |
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
|