09:00-10:15

Tutorial

● Self-stabilization: Past, Present, Future
Joffroy Beauquier

10:15-10:45

Break

10:45-12:00

Tutorial

● Security and Composition of Cryptographic Proctocols
Ran Canetti

12:00-14:50

Sight seeing

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

14:50-15:10

Coffee break

15:10-15:25

Opening remarks

Session Chair:
Mark  Tuttle

15:25-16:10

Invited talk 1

Session Chair:
Mark  Tuttle

● Over Two Decades of Research on Networking Games
Ariel Orda

16:10-16:30

Break

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

17:45-18:00

P2P

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

18:00-19:00

Posters session

19:00-21:00

Reception

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

Break

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:
Joan Feigenbaum

● 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

Break

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

Break

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

Break

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

Security

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

Break

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)

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

Break

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