Conference Program

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

(PODC 2005)

Sunday, July 17th, 2005

18:00-21:00 Reception (sponsored by Google)

Monday, July 18th, 2005

7:30- 8:20 Continental Breakfast

8:20-10:10 Session 1: Verification and Security (Session chair: Boaz Patt-Shamir, Tel-Aviv U.)

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

Proof Labeling Schemes
Amos Korman, Shay Kutten and David Peleg

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

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

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

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

10:10-10:30 Break

10:30-12:10 Session 2: Joint Session (Session chair: James Aspnes, Yale U.)

Distance Estimation and Object Location via Rings of Neighbors
Aleksandrs Slivkins

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

(SPAA) Coloring Unstructured Radio Networks
Thomas Moscibroda and Roger Wattenhofer

(SPAA) Name Independent Routing for Growth Bounded Networks
Ittai Abraham and Dahlia Malkhi

12:10-13:45 Lunch

13:45-15:35 Session 3: Distributed Data Structures (Session chair: Dahlia Malkhi, Microsoft Research and Hebrew U.)

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

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

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

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

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

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

15:35-16:05 Break

16:05-17:35 Session 4: Optimization (Session chair: Jared Saia, UNM)

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

Facility Location: Distributed Approximation
Thomas Moscibroda and Roger Wattenhofer

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

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

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: Distributed Algorithmic Mechanism Design for Scheduling
Thomas E. Carroll and Daniel Grosu

17:35-18:00 Poster Session

20:00-22:00 Business Meeting and Rump Session

Tuesday, July 19th, 2005

7:30- 8:20 Continental Breakfast

8:20-10:10 Session 5: Radio Networks (Session chair: Bogdan Chlebus, UC Denver)

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

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

Maximal Independent Sets in Radio Networks
Thomas Moscibroda and Roger Wattenhofer

On Selection Problem in Radio Networks
Dariusz Kowalski

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

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

10:10-10:40 Break

10:40-11:40 Invited Talk

Elias Koutsoupias

11:40-13:45 Lunch

13:45-15:35 Session 6: Consensus (Session chair: Rachid Guerraoui, EPFL)

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

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

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

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

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

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

15:35-16:05 Break

16:05-17:35 Session 7: Routing (Session chair: Marcos Aguilera, HP Labs)

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

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

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

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

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

17:45-18:45 Awards Ceremony and Dijkstra Prize Lecture

19:00-22:00 Banquet

Wednesday, July 20th, 2005

8:20-10:10 Session 8: Contention (Session chair: Mark Moir, Sun Microsystems)

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

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

Stochastic Analysis of Distributed Deadlock Scheduling
Yibei Ling and Shigang Chen

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

10:10-10:30 Break

10:30-12:10 Session 9: Joint Session (Session chair: Paul Spirakis, U. Patras)

Adaptive Routing with Stale Information
Simon Fischer and Berthold Vocking

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

(SPAA) Using Elimination to Implement Scalable FIFO Queues
Mark Moir, Daniel Nussbaum, Ori Shalev and Nir Shavit

(SPAA) Collaborate with Strangers to Find Own Preferences
Baruch Awerbuch, Yossi Azar, Zvi Lotker, Boaz Patt-Shamir and Mark Tuttle

12:10-13:45 Lunch

13:45-15:15 Session 10: Peer-to-Peer (Session chair: Haifeng Yu, Intel Research Pittsburgh)

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

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

On the Establishment of Distinct Identities in Overlay Networks
Rida Bazzi and Goran Konjevod

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

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

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

15:15-15:45 Break

15:45-17:15 Session 11: Broadcast (Session chair: Shlomi Dolev, Ben-Gurion U.)

Simultaneous Broadcast Revisited
Alejandro Hevia and Daniele Micciancio

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

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

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

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

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

[PODC 2005 Main Page]

Last modified: Tue Jun 7 14:13:20 EST 2005