23rd Annual ACM SIGACT-SIGOPS Symposium on
Principles Of Distributed Computing

(PODC 2004)

July 25-28, 2004, St. John's, Newfoundland, Canada

The time allocated to a regular paper is 25 minutes including questions and answers. It is suggested that a presenter plans for a 20 minutes presentation, and leaves 5 minutes for questions and answers. The time for a brief announcement presentation is 5 minutes, and it is suggested that questions and answers will be taken off line.

Sunday, 25 July 2004



Self-stabilization: Past, Present, Future
Joffroy Beauquier






Security and Composition of Cryptographic Proctocols
Ran Canetti


Sight seeing

and a boxed Lunch on a spectacular shore (not included in the registration)


Coffee break



Opening remarks

Session Chair:
Mark  Tuttle



Invited talk 1

Session Chair:
Mark  Tuttle

Over Two Decades of Research on Networking Games
Ariel Orda




16:30-17:45 Game Theory


Session Chair:
Idit Kedar

Coalition-Safe Cheap Talk
Matt Lepinski, Silvio Micali, Chris Peikert, Abhi Shelat

Mechanism Design for Policy Routing
Joan Feigenbaum, Rahul Sami, Scott Shenker

Selfish Caching in Distributed Systems: A Game-Theoretic Analysis
Byung-Gon Chun, Kamalika Chaudhuri, Hoeteck Wee, Marco Barreno, Christos Papadimitriou, John Kubiatowicz



Session Chair:
Idit Kedar


Brief Announcement: Network Limitations on Locality in Peer-to-peer Networks
Kirsten Hildrum, John Kubiatowicz, Jeremy Stribling

Brief Announcement: Prefix Hash Tree: An Indexing Data Structure for Distributed Hash Tables
Sriram Ramabhadran, Sylvia Ratnasamy, Joseph Hellerstein, Scott Shenker

Brief Announcement: On the Inherent Cost of Generic Broadcast
Fernando Pedone, Andre Schiper


Posters session




and posters

Monday, 26 July 2004


Invited talk 2

Session Chair:
Christof Fetzer


Concurrency: From PODC to J2SE, and Back
Doug Lea


Shared Memory Objects

Session Chair:
Christof Fetzer

Bringing Practical Lock-Free Synchronization to 64-Bit Applications
Simon Doherty, Maurice Herlihy, Victor Luchangco, Mark Moir

An Almost Non-blocking Stack
Hans-J. Boehm




Shared Memory Objects

Session Chair:
Victor Luchangco

Lock-Free Linked Lists and Skip Lists
Mikhail Fomitchev, Eric Ruppert

Lower Bounds for Adaptive Collect and Related Objects
Hagit Attiya, Faith Fich, Yaniv Kaplan

Efficient Synchronous Snapshots
Alex Brodsky, Faith Fich

On the Inherent Weakness of Conditional Synchronization Primitives
Faith Fich, Danny Hendler, Nir Shavit


Lunch (provided by PODC)


Shared Memory Objects

Session Chair:
Joan Feigenbaum


Brief Announcement: A Single-Enqueuer Wait-free Queue Implementation.
Matei David

Brief Announcement: Constraint-based Synchronization and Verification of Distributed Java Programs
Rafael Ramirez, Juanjo Martinez, Andrew Santosa

Brief Announcement: Completing the Lock-Free Dynamic Cycle
Maged Michael

Brief Announcement: Implementing Multi-Word Atomic Snapshots on Current Hardware
Chris Purcell, Tim Harris


Game Theory

Session Chair:


Specification Faithfulness in Networks with Rational Nodes
Jeffrey Shneidman, David Parkes

On the Expected Payment of Mechanisms for Task Allocation
Artur Czumaj, Amir Ronen

On Spectrum Sharing Games
Magnus Haldorsson, Li Li, Vahab Mirrokni




Internet Applications

Session Chair: Michael Mitzenmacher

Brief Announcement: Exposing and Eliminating Vulnerabilities to Denial of Service Attacks in Secure Gossip-Based Multicast
Gal Badishi, Idit Keidar, Amir Sasson

Load Balancing and Locality in Range-Queriable Data Structures
James Aspnes, Jonathan Kirsch, Arvind Krishnamurthy

Brief Announcement: Anti-Spoofing Prevention Method
Anat Bremler-Barr, Hanoch Levy

Choosing a Random Peer
Valerie King, Jared Saia

Brief Announcement: Concurrent Maintenance of Rings
Xiaozhou Li, Jayadev Misra, Greg Plaxton

Bounds for the Convergence Rate of Randomized Local Search in a Multiplayer Load-Balancing Game
Paul Goldberg


Dinner (on your own)


Business Meeting
and Rump Session

Tuesday, 27 July 2004


Routing and Self- Stabilization

Session Chair: Toshimitsu Masuzawa


Brief Announcement: Self-stabilizing Distance-d Distinct Labels via Enriched Fair Composition
Lisa Higham, Lixiao Wang

Brief Announcement: STALK: A Self-Stabilizing Hierarchical Tracking Service for Sensor Networks
Murat Demirbas, Anish Arora, Tina Nolte, Nancy Lynch

Brief Announcement: Linear Time Byzantine Self-Stabilizing Clock Synchronization
Ariel Daliot, Danny Dolev, Hanna Parnas

Compact Routing on Euclidean Metrics
Ittai Abraham, Dahlia Malkhi

When Graph Theory Helps Self-Stabilization
Christian Boulinier, Franck Petit, Vincent Villain

Efficient Algorithms for Constructing (1+\epsilon,\beta)-Spanners inthe Distributed and Streaming Models
Michael Elkin, Jian Zhang




Networks Graphs and Network Algorithms

Session Chair:
Boaz Patt-Shamir

Eclecticism Shrinks the World
Pierre Fraigniaud, Cyril Gavoille, Christophe Paul

Analyzing Kleinberg's (and other) Small-World Models
Charles Martel, Van Nguyen

Tradeoff Between Stretch Factor and Load Balancing Ratio in Routing on Growth Restricted Graphs
Jie Gao, Li Zhang

Brief Announcement: Randomized Rumor Spreading with Fewer Phone Calls
Kirsten Hildrum, Sean Ma, Satish Rao

Brief Announcement: An Incremental Algorithm for Calculation of Backup-Paths
Pierre Fransson, Lenka Carr-Motyckova

Brief Announcement: Name Independent Compact Routing In Trees
Kofi Laing


Lunch (on your own)


P2P and Network Algorithms

Session Chair:
Jim Aspnes

A Randomized ID Selection Algorithm for Peer-to-Peer Networks
Gurmeet Singh Manku

Brief Announcement: Towards a Secure Indirection Infrastructure
Karthik Lakshminarayanan, Daniel Adkins, Adrian Perrig, Ion Stoica

Efficient Top-K Query Calculation for Distributed Networks
Pei Cao, Zhe Wang

Brief Announcement: Trilix: A Scalable Lookup System for Dynamic Environments
Idit Keidar, Roie Melamed

On the Design of Distributed Protocols from Differential Equations
Indranil Gupta

Brief Announcement: Virtual Mobile Nodes for Mobile Ad Hoc Networks
Shlomi Dolev, Seth Gilbert, Nancy Lynch, Elad Schiller, Alex Shvartsman, Jennifer Welch




Distributed Applications, Distributed Memory , and Internet Applications

Session Chair:
Michel Raynal

Byzantine Disk Paxos: Optimal Resilience with Byzantine Shared Memory
Ittai Abraham, Gregory Chockler, Idit Keidar, Dahlia Malkhi

Brief Announcement: Reconfigurable Byzantine-Fault-Tolerant Atomic Memory
Rodrigo Rodrigues, Barbara Liskov

How Fast Can a Distributed Read Be?
Partha Dutta, Rachid Guerraoui, Ron Levy, Arindam Chakraborty

Brief Announcement: Adaptive Balancing Networks
Srikanta Tirthapura

Signed Quorum Systems
Haifeng Yu

Brief Announcement: Building an Adaptive Distributed Web Server System on the Fly for Handling Web Hotspots
Weibin Zhao, Henning Schulzrinne

Brief Announcement: The Design of an Internet-Scale Monitoring and Assertion-Checking Infrastructure
Monica Brockmeyer, Chunbo Chu

Brief Announcement: Cataclysm: Handling Extreme Overload in Internet Services
Bhuvan Urgaonkar, Prashant Shenoy


Banquet and Award Ceremony

Wednesday, July 28 2004



Session Chair:
Roger Wattenhofer

Asynchronous Group Key Exchange with Failures
Christian Cachin, Reto Strobl

Brief Announcement: RT Oblivious Erasure Correcting
Amos Beimel, Shlomi Dolev, Noam Singer

Brief Announcement: Secret Handshakes from CA-oblivious Encryption
Claude Castelluccia, Stanislaw Jarecki, Gene Tsudik

Brief Announcement: Detecting Malicious Routers

Alper Mizrak, Keith Marzullo, Stefan Savage


Wireless and Sensors

Session Chair:
Roger Wattenhofer

Competitive On-Line Paging Strategies for Mobile Users Under Delay Constraints
Amotz Bar-Noy, Yishay Mansour

Better Wake-up in Radio Networks
Bogdan Chlebus, Dariusz Kowalski

Brief Announcement: Optimal Asynchronous Garbage Collection for Checkpointing Protocols with Rollback-Dependency Trackability
Rodrigo Schmidt, Islene Garcia, Fernando Pedone, Luiz Buzato

Broadcast in Radio Networks Tolerating Byzantine Adversarial Behavior
Chiu-Yuen Koo




Wireless and Sensor

Session Chair: Panagiota Fatourou

A Note on Efficient Aggregate Queries in Sensor Networks
Boaz Patt-Shamir

Computation in Networks of Passively Mobile Finite-State Sensors
Dana Angluin, James Aspnes, Zoe Diamadi, Michael Fischer, Rene Peralta

What Cannot Be Computed Locally!
Fabian Kuhn, Thomas Moscibroda, Roger Wattenhofer

Brief Announcement: Degree-Optimal Deterministic Routing for P2P Systems
Gennaro Cordasco, Luisa Gargano, Mikael Hammar, Vittorio Scarano

Brief Announcement: Efficient Clustering in Unstructured Radio Networks
Fabian Kuhn, Thomas Moscibroda, Roger Wattenhofer

Brief Announcement: Polygonal Broadcast, Secret Maturity and the Firing Sensors
Shlomi Dolev, Ted Herman, Limor Lahiani


Lunch (provided by PODC)

13:35-14:50 Wireless

Session Chair: Gregory Chockler

Geometrically Aware Communication in Random Wireless Networks
Gady Kozma, Zvi Lotker, Micha Sharir, Gideon Stupp

Failure Detectors

Session Chair: Gregory Chockler

Gradient Clock Synchronization
Rui Fan, Nancy Lynch

Communication-Efficient Leader Election and Consensus with Limited Link Synchrony
Marcos Aguilera, Carole Delporte-Gallet, Hugues Fauconnier, Sam Toueg




Failure Detectors

Session Chair:
Alex  Shvartsman

The Weakest Failure Detectors to Solve Certain Fundamental Problems in Distributed Computing
Carole Delporte-Gallet, Hugues Fauconnier, Rachid Guerraoui, Vassos Hadzilacos, Petr Kouznetsov, Sam Toueg

Group Membership: A Novel Approach and the First Single-Round Algorithm
Roger Khazan

Brief Announcement: On the Possibility of Consensus in Asynchronous Systems with Finite Average Response Times
Christof Fetzer, Ulrich Schmid

Brief Announcement: The Synchronous Condition-Based Consensus Hierarchy
Achour Mostefaoui, Sergio Rajsbaum, Michel Raynal

Brief Announcement: Efficient Implementation of a Byzantine Data Storage System
Rida Bazzi, Yin Ding

Brief Announcement: On the Round Complexity of Distributed Consensus over Synchronous Networks
V. Muthuramakrishnan, D.V.S. Ravikant, V. Srikanth, K. Srinathan, C. Pandu Rangan

Brief Announcement: On the Respective Power of <>P and <>S to Solve One-Shot Agreement Problems
Roy Friedman, Achour Mostefaoui, Michel Raynal

[PODC 2004 Main Page]

This page is still under construction!

Last modified: Mon Jun 21 12:20:14 EST 2004