PODC 2008






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 
          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 
          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
          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
          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  
12:25     Dynamic Service Assignment in Next-Generation Mobile Networks: the MAGMA 
          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 
          Colette Johnen and Lisa Higham
12:25     Optimal Failure Detection with Low Sporadic Overhead and Communication 
          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

DIALM-POMC workshop