List of Accepted Papers

24th Annual ACM SIGACT-SIGOPS Symposium on
Principles Of Distributed Computing

(PODC 2005)


Full paper track (in no particular order)

Facility Location: Distributed Approximation
Thomas Moscibroda and Roger Wattenhofer

Routing Complexity of Faulty Networks
Omer Angel, Itai Benjamini, Eran Ofek and Udi Wieder

Stochastic Analysis of Distributed Deadlock Scheduling
Yibei Ling and Shigang Chen

Efficient Lookup on Unstructured Topologies
Ruggero Morselli, Bobby Bhattacharjee, Michael A. Marsh and Aravind Srinivasan

Efficient Dependency Tracking for Relevant Events in Shared-Memory Systems
Anurag Agarwal and Vijay K. Garg

Feasibility and Complexity of Broadcasting with Random Transmission Failures
Andrzej Pelc and David Peleg

Primal-Dual Based Distributed Algorithms for Vertex Cover with Semi-Hard Capacities
F. Grandoni, J. Konemann, A. Panconesi and M. Sozio

Correctness of a Gossip Based Membership Protocol
Andre Allavena, Alan Demers and John Hopcroft

Policy-Hiding Access Control in Open Environment
Jiangtao Li and Ninghui Li

Building Scalable and Robust Peer-toPeer Overlay Networks for Broadcasting using Network Coding
Kamal Jain, Laszlo Lovasz and Philip A. Chou

Maximal Independent Sets in Radio Networks
Thomas Moscibroda and Roger Wattenhofer

Advanced Contention Management for Dynamic Software Transactional Memory
William N. Scherer III and Michael L. Scott

Efficient Multi-Word Locking Using Randomization
Phuong Hoai Ha, Philippas Tsigas, Mirjam Wattenhofer and Roger Wattenhofer

Simultaneous Broadcast Revisited
Alejandro Hevia and Daniele Micciancio

Faster Communication in Known Topology Radio Networks
Leszek Gasieniec, David Peleg and Qin Xin

Fast fault-tolerant agreement algorithms
Carole Delporte-Gallet, Hugues Fauconnier, Stephanie Horn and Sam Toueg

Proof Labeling Schemes
Amos Korman, Shay Kutten and David Peleg

The Combined Power of Conditions and  Failure Detectors to Solve  Asynchronous Set Agreement
Achour Mostefaoui, Sergio Rajsbaum and Michel Raynal

On the establishment of distinct identities in overlay networks
Rida Bazzi and Goran Konjevod

Distance Estimation and Object Location via Rings of Neighbors
Aleksandrs Slivkins

On Selection Problem in Radio Networks
Dariusz Kowalski

On Reliable Broadcast in a Radio Network
Vartika Bhandari and Nitin H. Vaidya

A Topological Characterization of Weakness
Cindy Eisner, Dana Fisman and John Havlicek

Adaptive Routing with Stale Information
Simon Fischer and Berthold Voecking

On the Locality of Bounded Growth
Fabian Kuhn, Thomas Moscibroda and Roger Wattenhofer

A Network Pricing Game for Selfish Traffic
Ara Hayrapetyan, Eva Tardos and Tom Wexler

Skip-Webs: Efficient Distributed Data Structures for Multi-Dimensional Data Sets
Lars Arge, David Eppstein and Michael Goodrich

A Scheme for Load Balancing in Heterogenous Distributed Hash Tables
George Giakkoupis and Vassos Hadzilacos

Quorum Placement in Networks
Anupam Gupta, Bruce Maggs,
Florin Oprea and Michael K. Reiter

Feedback Control for Router Congestion Resolution
Xiaojie Gao and Leonard J. Schulman

Competitive Weighted Throughput Analysis of Greedy Protocols on DAGs
Eyal Gordon and Adi Rosen

Toward a Theory of Transactional Contention Managers
Rachid Guerraoui, Maurice Herlihy and Bastian Pochon

Consensus and Collision Detectors in Wireless Ad Hoc Networks
Gregory Chockler,  Murat Demirbas, Seth Gilbert, Calvin Newport and Tina Nolte

The weakest failure detector to solve nonuniform consensus.
Jonathan Eisler, Vassos Hadzilacos and Sam Toueg

Reliable Broadcast in Unknown Fixed-Identity Networks
Lakshminarayanan Subramanian, Randy H. Katz, Volker Roth, Scott Shenker and Ion Stoica

The Price of Selfish Behavior in Bilateral Network Formation
Jacomo Corbo and David C. Parkes

Brief announcement track (in no particular order)

Brief Announcement: Virtual Stationary Automata for
Mobile Networks
Shlomi Dolev, Seth Gilbert, Limor Lahiani, Nancy Lynch and Tina Nolte

Brief Announcement: Exploring the consistency problem space
Nishith Krishna, Marc Shapiro and Karthik Bhargavan

Brief Announcement: Ring-like DHTs and the Postage Stamp Problem
Mahadev Konar and Alexander E. Mohr

Brief Announcement: Coupling for Markov Decision Processes: Application to Self-Stabilization with Arbitrary Schedulers
Laurent Fribourg and Stephane Messika

Brief Announcement: Minimal System Conditions to Implement Unreliable Failure Detectors
Antonio Fernendez, Ernesto  Jimenez and Sergio Arevalo

Brief Announcement: Continuous Containment and Local Stabilization in Path-vector Routing
Hongwei Zhang and Anish Arora

Brief Announcement: Dynamic Interoperable Point-to-Point Connection of MPI Implementations
Michal Kouril and Jerome L. Paul

Brief Announcement: On the Possibility and the Impossibility of Message-Driven Self-Stabilizing Failure Detection
Martin Hutle and Josef Widder

Brief Announcement: Distributed Algorithmic Mechanism Design for Scheduling
Thomas E. Carroll and Daniel Grosu

Brief Announcement: Gradient Clock Synchronization in Sensor Networks
Lennart Meier and Lothar Thiele

Brief Announcement: Analysis of a Randomized Contention-Resolution Protocol for Distributed Access
Gopal Pandurangan and
Gahyun Park

Brief Announcement: Improved Asynchronous Group Mutual Exclusion
David Lin, Teng-Sheng Moh and Melody Moh

Brief Announcement: An Incentive-compatible Capacity Assignment Algorithm for Bulk Data Distribution Using P2P
Simon G. M. Koo, C. S. George Lee and Karthik Kannan

Brief Announcement: A Flexible Framework for Secret Handshakes
Gene Tsudik and Shouhuai Xu

Brief Announcement: Wait-Free Implementation of Multiple-Writers/Multiple-Readers Atomic Byzantine Data Storage Systems
Rida Bazzi and Yin Ding

Brief Announcement: The Overlay Network Content Distribution Problem
Chip Killian, Michael Vrable, Alex C. Snoeren, Amin Vahdat and Joseph Pasquale

Brief Announcement: Abstractions for Implementing Atomic Objects in Dynamic Systems
Roy Friedman, Michel Raynal and Corentin Travers

Brief Announcement: Controlled Quorum Selection in Arbitrary Topologies
Xinjie Li and Monica Brockmeyer

Brief Announcement: On the Expected Overpayment of VCG Mechanisms in Large Networks
David R. Karger and Evdokia Nikolova

Brief Announcement: Strong Detection of Misconfigurations
Raj Kumar Rajendran, Vishal Misra and Dan Rubenstein

Brief Announcement: Evaluation of Tree-based Data Gathering Algorithms for Wireless Sensor Networks
Marie Dumont, Melody Moh and Teng-Sheng Moh

Brief Announcement: Broadcast in Radio Networks in the presence of Byzantine Adversaries
Vinod Vaikuntanathan


[PODC 2005 Main Page]

Last modified: Tue Apr 26 2005