Copyright (c) Steve Pierpoint




Papers Accepted to PODC 2009

The Wireless Synchronization Problem
Shlomi Dolev, Seth Gilbert, Rachid Guerraoui, Fabian Kuhn, Calvin Newport

Energy and time efficient broadcasting in known topology radio networks with long-range interference
Frantisek Galcik, Leszek Gasieniec, Andrzej Lingas

Tight Bounds for Clock Synchronization
Christoph Lenzen, Thomas Locher, Roger Wattenhofer

The Effect of Power-Law Degrees on the Navigability of Small Worlds
Pierre Fraigniaud, George Giakkoupis

Fast Distributed Random Walks 
Atish Das Sarma, Danupon Nanongkai, Gopal Pandurangan

Simple and Efficient Asynchronous Byzantine Agreement with Optimal Resilience
Arpita Patra, Ashish Choudhary, C. Pandu Rangan

Concurrent Imitation Dynamics in Congestion Games
Heiner Ackermann, Petra Berenbrink, Simon Fischer, Martin Hoefer

SINR Diagrams: Towards Algorithmically Usable SINR Models of Wireless Networks
Chen Avin, Yuval Emek, Erez Kantor, Zvi Lotker, David Peleg, Liam Roditty

The Forgiving Graph: A distributed data structure for low stretch under adversarial attack
Tom Hayes, Jared Saia, Amitabh Trehan

Max registers, counters, and monotone circuits
James Aspnes, Hagit Attiya, Keren Censor

A Polylogarithmic Time Construction for Distributed Self-Stabilizing Skip Graphs
Riko Jacob, Andrea Richa, Christian Scheideler, Stefan Schmid, Hanjo Täubig

Parsimonious Flooding in Dynamic Graphs
Hervé Baumann, Pierluigi Crescenzi, Pierre Fraigniaud

Dynamic Atomic Storage Without Consensus
Marcos Aguilera, Idit Keidar, Dahlia Malkhi, Alexander Shraer

Coloring Unstructured Wireless Multi-Hop Networks
Johannes Schneider, Roger Wattenhofer

The flip Markov chain and a randomising P2P protocol
Colin Cooper, Martin Dyer, Andrew J. Handley

Correctness of Gossip-Based Membership under Message Loss
Maxim Gurevich, Idit Keidar

Oblivious Interference Scheduling
Alexander Fanghänel, Thomas Keßelheim, Harald Räcke, Berthold Vöcking

Extracting Quorum Failure Detectors
Vibhor Bhatt, Nicholas Christman, PPrasad Jayanti

Bounding the Locality of Distributed Routing Algorithms
Prosenjit Bose, Paz Carmi, Stephane Durocher

Return of the Primal-Dual: Distributed Metric Facility Location
Saurav Pandit, Sriram Pemmaraju

Partial Synchrony Based on Set Timeliness
Marcos K. Aguilera, Carole Delporte-Gallet, Hugues Fauconnier, Sam Toueg

Distributed and Parallel Algorithms for Weighted Vertex Cover and other Covering Problems
Christos Koufogiannakis, Neal E. Young

Fast scalable deterministic consensus for crash failures
Bogdan S. Chlebus, Dariusz R. Kowalski, Michal Strojnowski

Randomized Mutual Exclusion in O(log N/loglog N) RMRs
Danny Hendler, Philipp Woelfel

Preventing versus Curing: Avoiding Conflicts in Transactional Memories
Aleksandar Dragojevic, Rachid Guerraoui, Anmol V. Singh, Vasu Singh

Load Balancing Without Regret in the Bulletin Board Model
Robert Kleinberg, Georgios Piliouras, Eva Tardos

The Weakest Failure Detector for Solving k-Set Agreement
Eli Gafni, Petr Kuznetsov

Brief Announcements

Stateless Distributed Algorithms for Generalized Packing Linear Programs
Baruch Awerbuch, Zhenghua Fu, and Rohit Khandekar

Concurrent Non-commutative Boosted Transactions
Eric Koskinen and Maurice Herlihy

Distributed Phase Synchronization of Dynamic Set of Processes
R.K. Shyamasundar and Shivali Agarwal

How to Speed-up Fault-Tolerant Clock Generation in VLSI Systems-on-Chip via Pipelining
Andreas Dielacher, Matthias F?gger, and Ulrich Schmid

Perfectly Secure Message Transmission in Directed Networks Re-Visited
Arpita Patra, Ashish Choudhary, and C. Pandu Rangan

Virtual World Consistency: a new Condition for STM Systems
Damien Imbs and Michel Raynal

The Price of Anonymity: Optimal Consensus despite Asynchrony, Crash and Anonymity
Francois Bonnet and Michel Raynal

A Note on Distributed Stable Matching
Alex Kipnis and Boaz Patt-Shamir

On a Selfish Caching Game
Pietro Michiardi, Carla-Fabiana Chiasserini, Claudio Casetti, Chi-Anh La, and Marco Fiore

Non-Self-Stabilizing and Self-Stabilizing Gathering in Networks of Mobile Agents - 
the Notion of Speed
Joffroy Beauquier, Janna Burman, Julien Clement, and Shay Kutten

The Disagreement Power of an Adversary
Carole Delporte-Gallet, Hugues Fauconnier, Rachid Guerraoui, and Andreas Tielmann

Minimum Spanning Trees and Cone-Based Topology Control
Alejandro Cornejo and Nancy Lynch

Optimization Based Rate Allocation for Application Layer Multicast
Jinyao Yan, Martin May, and Bernhard Plattner

Weakest failure detectors via an egg-laying simulation
Antonio Fern?ndez, Sergio Rajsbaum, Corentin Travers

Locality-Based Aggregate Computation in Wireless Sensor Networks
Jen-Yeu Chen, Gopal Pandurangan, and Jianghai Hu

Tight Lower Bounds for Greedy Routing in Uniform Small World Rings
Martin Dietzfelbinger and Philipp Woelfel

Optimal Self-stabilizing Multi-token Ring: A Randomized Solution
Anurag Dasgupta, Sukumar Ghosh, and Andrew Berns 

Fast Scalable Byzantine Agreement in the Full Information Model with a Nonadaptive Adversary  
Valerie King and Jared Saia

Push: a DISC shell
Eric Van Hensbergen and Noah Evans

Deaf, Dumb, and Chatting Robots: Enabling Distributed Computation & Fault-Tolerance 
Among Stigmergic Robots
Yoann Dieudonn?, Shlomi Dolev, Franck Petit, and Michael Segal

Global Consistency can be Easier than Point-to-Point Communication
Prasant Gopal, Anuj Gupta, Pranav K. Vasishta, Piyush Bansal, and Kannan Srinathan

Hardness of Broadcasting in Wireless Networks with Unreliable Communication
Fabian Kuhn, Nancy Lynch, and Calvin Newport

Topology Knowledge Affects Probabilistic Reliable Communication
Pranav K. Vasishta, Prasant Gopal, Anuj Gupta, Piyush Bansal, and Kannan Srinathan

A Platform for Experimenting with Mobile Algorithms in a Laboratory
Matthieu Roy and Marc-Olivier Killijian

The Theory Of Network Tracing
H. B. Acharya and M. G. Gouda

(More) Efficient Pruning of Ad-Hoc Wireless Networks
Enoch Peserico

Self-Assembly as Graph Grammar as Distributed System
Aaron Sterling

Distributed Discovery of Large Near-Cliques
Zvika Brakerski and Boaz Patt-Shamir

Lightweight Key Agreement and Digital Certificates for Wireless Sensor Networks
Oscar Garcia-Morchon, Tobias Heer, Ludo Tolhuizen, and Klaus Wehrle

Distributed Algorithms for Approximating Wireless Network Capacity
Michael Dinitz

New Bounds for the Controller Problem
Yuval Emek and Amos Korman

Complexity Analysis and Algorithm Design for Pipeline Configuration in Distributed Networks
Yi Gu, Qishi Wu, Anne Benoit, and Yves Robert

Exactly Electing a Unique Leader is not Harder than Computing Symmetric Functions 
on Anonymous Quantum Networks
Hirotada Kobayashi, Keiji Matsumoto, and Seiichiro Tani

Impossibility Results for OptimisticFair Exchange with Multiple Autonomous Arbiters
Alptekin K?p?? and Anna Lysyanskaya

Collaborative Measurement of Upload Speeds in P2P Systems
John R. Douceur, James Mickens, Thomas Moscibroda, and Debmalya Panigrahi

Vertical Paxos and Primary-Backup Replication
Leslie Lamport, Dahlia Malkhi, and Lidong Zhou