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
Lunch (on your own)	12:00-1:30PM
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