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
    TBA
    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