Sunday August 17
17:30-19:30 Welcome reception in the Debates Room of Hart House (see map)
Monday August 18
08:20 Breakfast
Invited Talk (Session chair: Boaz Patt-Shamir)
08:50 Accountability for Distributed Systems
Peter Druschel
09:50 Coffee Break
Regular Papers (Session chair: Adi Rosen)
10:10 Distributed Computation of the Mode
Fabian Kuhn, Thomas Locher and Stefan Schmid
10:35 Sublogarithmic Distributed MIS Algorithm for Sparse Graphs
using Nash-Williams Decomposition
Leonid Barenboim and Michael Elkin
11:00 A Log-Star Distributed Maximal Independent Set Algorithm
for Growth Bounded Graphs
Johannes Schneider and Roger Wattenhofer
11:25 A Jamming-Resistant MAC Protocol for Single-Hop Wireless Networks
Baruch Awerbuch and Andrea Richa and Christian Scheideler
Brief announcements (Session chair: Boaz Patt-Shamir)
12:00 Forget him and keep on moving
Augustin Chaintreau, Pierre Fraigniaud and Emmanuelle Lebhar
12:05 Online and Dynamic Embeddings of Approximate Ultrametrics
Michael Dinitz
12:10 Dynamic Routing and Location Services in Metrics of Low Doubling Dimension
Goran Konjevod, Andrea Richa and Donglin Xia
12:15 On ad hoc routing with guaranteed delivery
Mark Braverman
12:20 On the Internet Delay Space Dimensionality
Bruno Abrahao and Robert Kleinberg
12:25 Maximizing Quorum Availability in Multi-Clustered Systems
Roman Vitenberg and Ricardo Jimenez-Peris
Brief announcements (Session chair: Mark Moir)
12:00 BMobi_Causal: A Causal Broadcast Protocol in Mobile Dynamic
Groups
Chafika BENZAID and Nadjib BADACHE
12:05 Correctness Criteria for Replicated Database Systems with
Snapshot Isolation Replicas
J.E. Armendáriz-Iñigo, J.R. Juárez-Rodríguez, J.R. González de Mendívil
and F.D. Muñoz-Escoí
12:10 The Asynchronous Bounded-Cycle Model
Peter Robinson and Ulrich Schmid
12:15 Model checking transactional memory with Spin
John O'Leary, Bratin Saha and Mark R. Tuttle
12:20 On the Robustness of (Semi) Fast Quorum-Based
Implementations of Atomic Shared Memory
Chryssis Georgiou, Nicolas C. Nicolaou and Alexander A. Shvartsman
12:25 Principles of Untrusted Storage: A New Look at Consistency Conditions
Christian Cachin, Idit Keidar and Alexander Shraer
12:30 Lunch
Regular Papers (Session chair: Sergio Rajsbaum)
14:20 Anti-Omega: the weakest failure detector for set agreement
Piotr Zielinski
14:45 Failure Detectors in Loosely Named Systems
Yehuda Afek and Israel Nir
15:10 Every Problem has a Weakest Failure Detector
Prasad Jayanti and Sam Toueg
15:35 Sharing is harder than agreeing
Carole Delporte and Hugues Fauconnier and Rachid Guerraoui
16:00 Coffee Break
Regular Papers (Session chair: Zvi Lotker)
16:20 Collaborative Enforcement of Firewall Policies in Virtual Private Networks
Alex X. Liu and Fei Chen
16:45 CAR-STM: Scheduling-Based Collision Avoidance and
Resolution for Software Transactional Memory
Shlomi Dolev, Danny Hendler and Adi Suissa
17:10 Secure Communication over Radio Channels
Shlomi Dolev and Seth Gilbert and Rachid Guerraoui and
Calvin Newport
17:35 On Tradeoff Between Network Connectivity, Phase Complexity and Communication
Complexity of Reliable Communication Tolerating Mixed Adversary
Ashwinkumar B V and Arpita Patra and Ashish Choudhary and
Kannan Srinathan and C. Pandu Rangan
Evening: Presentation of Dijkstra Prize and Business Meeting
Tuesday August 19
08:20 Breakfast
08:50 Invited talk (Session chair: Boaz Patt-Shamir)
Beyond Nash Equilibrium: Solution Concepts for the 21st Century
Joe Halpern
09:50 Coffee Break
Regular Papers (Session chair: Fabian Kuhn)
10:10 On the Complexity of Asynchronous Gossip
Chryssis Georgiou, Seth Gilbert, Rachid Guerraou and Dariusz R. Kowalski
10:35 Brahms: Byzantine Resilient Random Membership Sampling
Edward Bortnikov, Maxim Gurevich, Idit Keidar, Gabriel Kliot and
Alexander Shraer
11:00 Efficient Randomised Broadcasting in Random Regular Networks with
Applications in Peer-to-Peer Systems
Petra Berenbrink, Robert Elsaesser and Tom Friedetzky
11:25 Bounded Budget Connection (BBC) games or How to make friends and influence
people, on a budget
Nikolaos Laoutaris, Laura Poplawski, Rajmohan Rajaraman, Ravi
Sundaram and Shang-Hua Teng
Brief announcements (Session chair: Cyril Gavoille)
12:00 Sliver: A Fast Distributed Slicing Algorithm
Vincent Gramoli, Ymir Vigfusson, Ken Birman, Anne-Marie Kermarrec and Robert
van Renesse
12:05 A dynamic exchange game
Laszlo Toka and Pietro Michiardi
12:10 Anonymous and Censorship-resistant Content-sharing in Unstructured Overlays
Michael Backes, Marek Hamerlik, Alessandro Linari, Matteo Maffei, Christos
Tryfonopoulos and Gerhard Weikum
12:15 Our Brothers' Keepers: Secure Routing with High Performance
Alex Brodsky
12:20 Distributed Churn Measurement for Arbitrary Networks
V. Gramoli, A.-M. Kermarrec and E. Le Merrer
12:25 Efficient Linear Pipeline Configuration in Distributed Heterogeneous
Computing Environments
Yi Gu, Qishi Wu, Mengxia Zhu and Nageswara S.V. Rao
Brief announcements (Session chair: Seth Gilbert)
12:00 A Tradeoff Analysis on Message Complexity and Lifetime Optimality for a
Distributed Multicast Algorithm in Wireless Sensor Networks
Song Guo and Victor Leung
12:05 Nearest-neighbor graphs on random point sets and their application to sensor
networks
Amitabha Bagchi and Sohit Bansal
12:10 From anarchy to geometric structuring: the power of virtual coordinates
Kermarrec A.-M., Mostefaoui A., Raynal M., Tredan G. and Viana A.
12:15 Balancing Energy Consumption for Data Gathering in Wireless Sensor Networks
Haibo Zhang and Hong Shen
12:20 Scheduling Sensors by Tiling Lattices
Andreas Klappenecker, Hyunyoung Lee and Jennifer L. Welch
12:25 Power Management of Devices: When Should I Switch Off?
Ajay Gulati
12:30 Lunch
Regular Papers (Session chair: Jennifer Lundelius Welch)
14:20 On A Capacitated Multivehicle Routing Problem
Xiaojie Gao and Leonard J. Schulman
14:45 Improved Compact Routing Schemes for Dynamic Trees
Amos Korman
15:10 Tight Bounds for Delay Sensitive Aggregation
Yvonne-Anne Oswald, Stefan Schmid and Roger Wattenhofer
15:35 The Forgiving Tree: A Self-Healing Distributed Data Structure
Tom Hayes, Navin Rustagi, Jared Saia and Amitabh Trehan
16:00 Coffee Break
Regular Papers (Session chair: Leszek Gasieniec)
16:20 Flooding Time in Markov-Dynamic Graphs
Andrea E.F. Clementi, Claudio Macci, Angelo Monti, Francesco
Pasquale and Riccardo Silvestri
16:45 On the Effect of the Deployment Setting on Broadcasting in Euclidean Radio
Networks
Yuval Emek, Erez Kantor and David Peleg
17:10 Virtual Infrastructure for Collision-Prone Wireless Networks
Gregory Chockler and Seth Gilbert and Nancy A. Lynch
17:35 Sleeping on the Job: Energy-Efficient Reliable Broadcast for Radio Networks
Valerie King, Cynthia Phillips, Jared Saia and Maxwell Young
Wednesday August 20
08:00 Breakfast
Regular Papers (Session chair: Zvi Lotker)
08:30 Distributed Algorithms for Ultrasparse Spanners and Linear Size Skeletons
Seth Pettie
08:55 Efficient Distributed Approximation Algorithms via Probabilistic Tree
Embeddings
Maleq Khan, Fabian Kuhn, Dahlia Malkhi, Gopal Pandurangan and
Kunal Talwar
09:20 On the Locality of Distributed Sparse Spanner Construction
Bilel Derbel, Cyril Gavoille, David Peleg and Laurent Viennot
09:45 The Stretched Exponential Distribution of Internet Media Access Patterns
Lei Guo, Enhua Tan, Songing Chen, Zhen Xiao and Xiaodong Zhang
10:10 Coffee Break
Regular Papers (Session chair: Rachid Guerraoui)
10:30 New Combinatorial Topology Upper and Lower Bounds for Renaming
Armando Castaneda and Sergio Rajsbaum
(best student paper award)
10:55 Timeliness-based wait-freedom: a gracefully degrading progress condition
Marcos K. Aguilera and Sam Toueg
11:20 Lower Bounds for Randomized Consensus under a Weak Adversary
Hagit Attiya and Keren Censor
11:45 Randomized Consensus with O(n log n) Individual Work
James Aspnes, Hagit Attiya and Keren Censor
12:10 Lunch
Afternoon: Nancy Lynch Celebration: Sixty and Beyond
Evening: Conference banquet
Thursday August 21
08:20 Breakfast
08:50 Invited talk (Session chair: Boaz Patt-Shamir)
The Internet is Flat: A brief history of networking over the next ten years
Don Towsley
09:50 Coffee Break
Regular Papers (Session chair: Cyril Gavoille)
10:10 Packet Mode and QoS Algorithms for Buffered Crossbar Switches with
FIFO Queuing
Alex Kesselman, Kirill Kogan and Michael Segal
10:35 The Impact of Randomization in Smoothing Networks
Marios Mavronicolas and Thomas Sauerwald
11:00 Optimizing Data Popularity Conscious Bloom Filters
Ming Zhong, Pin Lu, Kai Shen and Joel Seiferas
11:25 Distributed Order Scheduling and its Application to Multi-Core DRAM Controllers
Thomas Moscibroda and Onur Mutlu
Brief announcements (Session chair: Leszek Gasieniec)
12:00 Greedy Distributed Optimization of Unsplittable Multi-Commodity Flows
Baruch Awerbuch and Rohit Khandekar
12:05 Stateless Distributed Algorithms for Near Optimal Maximum Multicommodity Flow
Baruch Awerbuch and Rohit Khandekar
12:10 Distributed Averaging in the presence of a sparse cut
Hariharan Narayanan
12:15 Gossip-based aggregate computation: computing faster with non address-
oblivious scheme
Roberto Di Pietro and Pietro Michiardi
12:20 Snap-Stabilization in Message-Passing Systems
Sylvie Delaet, Stephane Devismes, Mikhail Nesterenko and Sebastien
Tixeuil
12:25 Dynamic Service Assignment in Next-Generation Mobile Networks: the MAGMA
Approach
Edward Bortnikov, Israel Cidon and Idit Keidar
Brief announcements (Session chair: Jennifer Lundelius Welch)
12:00 Quantum Distributed Consensus
Louis Helm
12:05 Looking for the Optimal Conditions for Solving Set Agreement
Francois Bonnet and Michel Raynal
12:10 Tight RMR Lower Bounds for Mutual Exclusion and Other Problems
Hagit Attiya, Danny Hendler and Philipp Woelfel
12:15 Closing the Complexity Gap Between FCFS Mutual Exclusion
and Mutual Exclusion
Robert Danek and Wojciech Golab
12:20 Fault-tolerant Implementations of Atomic Registers by Safe Registers in
Networks
Colette Johnen and Lisa Higham
12:25 Optimal Failure Detection with Low Sporadic Overhead and Communication
Locality
Alberto Lafuente, Mikel Larrea, Iratxe Soraluze and Roberto Cortiñas
12:30 Lunch
14:00 Invited talk
Knowledge and Information in Probabilistic Systems
Prakash Panangaden
15:00 Coffee Break
Brief announcements (Session chair: Eric Ruppert)
15:20 Optimizing Consistency Checking for Memory-Intensive
Transactions with DracoSTM
Justin Gottschlich and Daniel A. Connors
15:25 Wait-free Programming for General Purpose Computations on Graphics Processors
Phuong Hoai Ha, Philippas Tsigas and Otto J. Anshus
15:30 Transactional Memory Retry Mechanisms
Michael F. Spear, Andrew Sveikauskas and Michael L. Scott
15:35 Scheduling Tasks with Dependencies on Asymmetric Multiprocessors: Energy &
Time Efficiency
Ioannis Chatzigiannakis, Georgios Giannoulis and Paul G. Spirakis
Brief announcements (Session chair: Adi Rosen)
15:20 The Lotus-Eater Attack
Ian A. Kash, Eric J. Friedman and Joseph Y. Halpern
15:25 Extracting models from design documents with Mapster
David James, Tim Leonard, John O'Leary, Murali Talupur and Mark R. Tuttle
15:30 Efficient Protocol for Single Phase Unconditionally Secure Message
Transmission with Optimum Communication Complexity
Kannan Srinathan, Ashish Choudhary, Arpita Patra and C. Pandu Rangan
15:35 Mobile Proactive Secret Sharing
David Schultz, Barbara Liskov and Moses Liskov
Regular Papers (Session chair: Yoram Moses)
15:50 Asynchronous Exclusive Selection
Bogdan S. Chlebus and Dariusz R. Kowalski
16:15 Fast Self-stabilizing Byzantine Tolerant Digital Clock Synchronization
Michael Ben-Or, Danny Dolev and Ezra N. Hoch
16:40 OCD: Obsessive Consensus Disorder (or Repetitive Consensus)
Danny Dolev and Ezra N. Hoch
17:05 An Almost-Surely Terminating Polynomial Protocol for Asynchronous Byzantine
Agreement with Optimal Resilience
Ittai Abraham, Danny Dolev and Joseph Y. Halpern
Friday August 22