PODC 2008





Papers Accepted to PODC 2008

Packet Mode and QoS Algorithms for Buffered Crossbar Switches with FIFO
Alex Kesselman and Kirill Kogan and Michael Segal

Flooding Time in Markov-Dynamic Graphs
Andrea E.F. Clementi and Claudio Macci and Angelo Monti and Francesco
Pasquale and Riccardo Silvestri

Anti-Omega: the weakest failure detector for set agreement
Piotr Zielinski

Distributed Computation of the Mode
Fabian Kuhn and Thomas Locher and Stefan Schmid

On the Effect of the Deployment Setting on Broadcasting in Euclidean Radio
Yuval Emek and Erez Kantor and David Peleg

Lower Bounds for Randomized Consensus under a Weak Adversary
Hagit Attiya and Keren Censor

VGuard: Collaborative Enforcement of Firewall Policies in Virtual Private
Alex X. Liu, and Fei Chen

Optimizing Data Popularity Conscious Bloom Filters
Ming Zhong and Pin Lu and Kai Shen and Joel Seiferas

Tight Bounds for Delay Sensitive Aggregation
Yvonne-Anne Oswald and Stefan Schmid and Roger Wattenhofer

Distributed Algorithms for Ultrasparse Spanners and Linear Size Skeletons
Seth Pettie

Failure Detectors in Loosely Named Systems
Yehuda Afek and Israel Nir

Sublogarithmic Distributed MIS Algorithm for Sparse Graphs using
Nash-Williams Decomposition
Leonid Barenboim and Michael Elkin

Improved Compact Routing Schemes for Dynamic Trees
Amos Korman

The Stretched Exponential Distribution of Internet Media Access Patterns
Lei Guo and Enhua Tan and Songing Chen and Zhen Xiao and Xiaodong Zhang

New Combinatorial Topology Upper and Lower Bounds for Renaming
Armando Castaneda and Sergio Rajsbaum

Timeliness-based wait-freedom: a gracefully degrading progress condition
Marcos K. Aguilera and Sam Toueg 

The Forgiving Tree: A Self-Healing Distributed Data Structure
Tom Hayes and Navin Rustagi and Jared Saia and Amitabh Trehan

CAR-STM: Scheduling-Based Collision Avoidance and Resolution for Software
Transactional Memory
Shlomi Dolev and Danny Hendler and Adi Suissa

On Tradeoff Between Network Connectivity, Phase Complexity and Communication
Complexity of  Reliable Communication Tolerating Mixed Adversary
AashwinKumar B. V and Arpita Patra and Ashish Choudhary and Kannan Srinathan
and C. Pandu Rangan

A Log-Star Distributed Maximal Independent Set Algorithm For Growth Bounded
Johannes Schneider and Roger Wattenhofer

On the Complexity of Asynchronous Gossip
Chryssis Georgiou and Seth Gilbert and Rachid Guerraoui and Dariusz R.

Virtual Infrastructure for Collision-Prone Wireless Networks
Gregory Chockler and Seth Gilbert and Nancy A. Lynch

On the Locality of Distributed Sparse Spanner Construction
Bilel Derbel and Cyril Gavoille and David Peleg and Laurent Viennot

Bounded Budget Connection (BBC) games or How to make friends and influence
people, on a budget
Nikolaos Laoutaris and Laura Poplawski and Rajmohan Rajaraman and Ravi
Sundaram and Shang-Hua Teng

Brahms: Byzantine Resilient Random Membership Sampling
Edward Bortnikov and Maxim Gurevich and Idit Keidar and Gabriel Kliot and
Alexander Shraer

A Jamming-Resistant MAC Protocol for Single-Hop Wireless Networks
Baruch Awerbuch and Andrea Richa and Christian Scheideler

Secure Communication over Radio Channels
Shlomi Dolev and Seth Gilbert and Rachid Guerraoui and Calvin Newport

Randomized Consensus with O(n log n) Individual Work
James Aspnes and Hagit Attiya and Keren Censor

Sleeping on the Job: Energy-Efficient Reliable Broadcast for Radio Networks
Valerie King and Cynthia Phillips and Jared Saia and Maxwell Young

The Impact of Randomization in Smoothing Networks
Marios Mavronicolas and Thomas Sauerwald

On A Capacitated Multivehicle Routing Problem
Xiaojie Gao and Leonard J. Schulman

Asynchronous Exclusive Selection
Bogdan S. Chlebus and Dariusz R. Kowalski

Every Problem has a Weakest Failure Detector
Prasad Jayanti and Sam Toueg

Fast Self-stabilizing Byzantine Tolerant Digital Clock Synchronization
Michael Ben-Or and Danny Dolev and Ezra N. Hoch

OCD: Obsessive Consensus Disorder (or Repetitive Consensus)
Danny Dolev and Ezra N. Hoch

Efficient Distributed Approximation Algorithms via Probabilistic Tree
Maleq Khan and Fabian Kuhn and Dahlia Malkhi and Gopal Pandurangan and
Kunal Talwar

Efficient Randomised Broadcasting in Random Regular Networks with
Applications in Peer-to-Peer Systems
Petra Berenbrink and Robert Elsaesser and Tom Friedetzky

Distributed Order Scheduling and its Application to Multi-Core DRAM
Thomas Moscibroda and Onur Mutlu

An Almost-Surely Terminating Polynomial Protocol for Asynchronous Byzantine
Agreement with Optimal Resilience
Ittai Abraham and Danny Dolev and Joseph Y. Halpern

Sharing is harder than agreeing
Carole Delporte and Hugues Fauconnier and Rachid Guerraoui

Brief Announcements

Quantum Distributed Consensus
Louis Helm

On ad hoc routing with guaranteed delivery
Mark Braverman

A Tradeoff Analysis on Message Complexity and Lifetime Optimality for a
Distributed Multicast Algorithm in Wireless Sensor Networks
Song Guo and Victor Leung

Looking for the Optimal Conditions  for Solving  Set Agreement
Francois Bonnet,  and Michel Raynal

BMobi_Causal: A Causal Broadcast Protocol in Mobile Dynamic Groups
Chafika BENZAID and Nadjib BADACHE

Nearest-neighbor graphs on random point sets and their application to sensor
Amitabha Bagchi and Sohit Bansal

The Lotus-Eater Attack
Ian A. Kash and Eric J. Friedman and Joseph Y. Halpern

Correctness Criteria for Replicated Database Systems with Snapshot Isolation
J.E. Armendariz-Inigo and J.R. Juarez-Rodriguez and J.R. Gonzalez de
Mendivil and F.D. Munoz-Escoi

Sliver: A Fast Distributed Slicing Algorithm
Vincent Gramoli and Ymir Vigfusson and Ken Birman and Anne-Marie Kermarrec
and Robert van Renesse

Brief Announcement: Optimizing Consistency Checking for Memory-Intensive
Transactions with DracoSTM
Justin Gottschlich and Daniel A. Connors

Greedy Distributed Optimization of Unsplittable Multi-Commodity Flows
Baruch Awerbuch and Rohit Khandekar

Scheduling Tasks with Dependencies on Asymmetric Multiprocessors: Energy &
Time Efficiency
Ioannis Chatzigiannakis and Georgios Giannoulis and Paul G. Spirakis

>From anarchy to geometric structuring:  the power of virtual coordinates
Kermarrec A.-M. and Mostefaoui A. and  Raynal M. and  Tredan G. and Viana A.

The Asynchronous Bounded-Cycle Model
Peter Robinson and Ulrich Schmid

Forget him and keep on moving
Augustin Chaintreau and Pierre Fraigniaud and Emmanuelle Lebhar

Brief announcement: A dynamic exchange game
Laszlo Toka and Pietro Michiardi

Anonymous and Censorship-resistant Content-sharing in Unstructured Overlays
Michael Backes and Marek Hamerlik and Alessandro Linari and Matteo Maffei
and Christos Tryfonopoulos and Gerhard Weikum

Optimal Failure Detection with Low Sporadic Overhead and Communication
Alberto Lafuente and Mikel Larrea and Iratxe Soraluze and Roberto CortiÓ±as

Extracting models from design documents with Mapster
David James and Tim Leonard and John O'Leary and Murali Talupur and Mark R.

Model checking transactional memory with Spin
John O'Leary and Bratin Saha and Mark R. Tuttle

Balancing Energy Consumption for Data Gathering in Wireless Sensor Networks
Haibo Zhang and Hong Shen

On the Robustness of (Semi)Fast Quorum-Based Implementations of Atomic
Shared Memory
Chryssis Georgiou and Nicolas C. Nicolaou and Alexander A. Shvartsman

Efficient Protocol for Single Phase Unconditionally Secure Message
Transmission with Optimum Communication Complexity
Kannan Srinathan and Ashish Choudhary and Arpita Patra and C. Pandu Rangan

Dynamic Service Assignment in Next-Generation Mobile Networks: the MAGMA
Edward Bortnikov and Israel Cidon and Idit Keidar

Online and Dynamic Embeddings of Approximate Ultrametrics
Michael Dinitz

Stateless Distributed Algorithms for Near Optimal Maximum Multicommodity
Baruch Awerbuch and Rohit Khandekar

Our Brothers' Keepers: Secure Routing with High Performance
Alex Brodsky

Scheduling Sensors by Tiling Lattices
Andreas Klappenecker and Hyunyoung Lee and Jennifer L. Welch

Maximizing Quorum Availability in Multi-Clustered Systems
Roman Vitenberg and Ricardo Jimenez-Peris

Tight RMR Lower Bounds for Mutual Exclusion and Other Problems
Hagit Attiya and Danny Hendler and Philipp Woelfel

Mobile Proactive Secret Sharing.
David Schultz and Barbara Liskov and Moses Liskov

Distributed Averaging in the presence of a sparse cut
Hariharan Narayanan

Brief Announcement: Closing the Complexity Gap Between FCFS Mutual Exclusion
and Mutual Exclusion
Robert Danek and Wojciech Golab

Dynamic Routing and Location Services in Metrics of Low Doubling Dimension
Goran Konjevod and Andrea Richa  and Donglin Xia

Gossip-based aggregate computation: computing faster  with non
address-oblivious scheme
Roberto Di Pietro and Pietro Michiardi

Snap-Stabilization in Message-Passing Systems
Sylvie Delaet and Stephane Devismes and Mikhail Nesterenko and Sebastien

Wait-free Programming for General Purpose Computations on Graphics
Phuong Hoai Ha and Philippas Tsigas and Otto J. Anshus

Principles of Untrusted Storage: A New Look at Consistency Conditions
Christian Cachin and Idit Keidar and Alexander Shraer

Fault-tolerant Implementations of Atomic Registers by Safe Registers in
Colette Johnen and Lisa Higham

Distributed Churn Measurement for Arbitrary Networks
V. Gramoli and A.-M. Kermarrec and E. Le Merrer

Brief Announcement: Transactional Memory Retry Mechanisms
Michael F. Spear and Andrew Sveikauskas and Michael L. Scott

On the Internet Delay Space Dimensionality
Bruno Abrahao and Robert Kleinberg

Efficient Linear Pipeline Configuration in Distributed Heterogeneous
Computing Environments
Yi Gu and Qishi Wu and Mengxia Zhu and Nageswara S.V. Rao

Power Management of Devices: When Should I Switch Off?
Ajay Gulati