Program for PODC 2003

Important note about timing: Regular talks (labelled with R) should be 22 minutes, with 3 minutes for questions and speaker change. Brief announcements (labelled with BA) should be 8 minutes, with 2 minutes for questions and speaker change. Due to a full schedule, speakers are requested to strictly adhere to these time limits.

July 13, 2003 - Sunday

Note: All Tutorials today will meet in Suffolk next to the registration area.
9:00am - 10:00am Registration
10:00am - 12:00pm Tutorial 1 - Chair: James Aspnes
Incentives and Internet Computation
Joan Feigenbaum (Yale) and Scott Shenker (ICSI)
12:00noon - 1:00pm Lunch (on your own)
1:00pm - 3:00pm Tutorial 2 - Chair: Gene Itkis
Content Protection Technologies
Jeffrey B. Lotspiech, Tushar Chandra, and Donald E. Leake, Jr. (IBM)
3:00pm - 3:10pm Break
3:10pm - 3:20pm Fischer Celebration Opening Remarks
Gadi Taubenfeld
3:20pm - 4:05pm Fischer Celebration Lecture 1
Title: M.J. Fischer, et al., The First Decade -- mid-60's to 70's
Albert Meyer, Massachusetts Institute of Technology
4:05pm - 4:50pm Fischer Celebration Lecture 2
Working with Mike on Distributed Computing Theory, 1978-1992
Nancy Lynch, Massachusetts Institute of Technology
4:50pm - 5:00pm Break
5:00pm - 5:45pm Fischer Celebration Lecture 3
Title: TBA
Leslie Lamport, Microsoft Research
5:45pm - 6:30pm Fischer Celebration Lecture 4
Fischer's Cryptographic Protocols
Rebecca Wright, Stevens Institute of Technology
6:45pm Buses leave from Sheraton Needham hotel for excursion
7:00pm - 10:00pm Excursion and reception dinner sponsored by Sun Microsystems Laboratories
Boston's Museum of Science - Skyline Room
10:30pm (approx) Buses return to Sheraton Needham hotel from excursion

July 14, 2003 - Monday

Note: All Sessions through the week, including the business meeting, will meet in the Ballroom
8:00am - 8:25am Breakfast (provided by PODC)
8:25am - 8:30am Opening Remarks
8:30am - 9:30am Invited Talk 1
Title: Data Streams, Message Brokers, Sensor Networks, and Other Strange Places for Database Query Processing
Michael Franklin, University of California at Berkeley
9:30am - 10:20am Session 1 - Chair: Rajmohan Rajaraman

R1: Constant-Time Distributed Dominating Set Approximation
Fabian Kuhn, Roger Wattenhofer
Winner of Best Student Paper Award

R2: Distributed Error Confinement
Yossi Azar, Shay Kutten, Boaz Patt-Shamir

10:20am - 10:40am Break
10:40am - 12:30pm Session 2 - Chair: Boaz Patt-Shamir

R3: Compact Roundtrip Routing with Topology-Independent Node Names
Marta Arias, Lenore Cowen, A. Kofi Laing

R4: A New Approach to On-Demand Loop-Free Routing in Ad Hoc Networks
J.J. Garcia-Luna-Aceves, Marc Mosko, Charles Perkins

R5: Geometric Ad-Hoc Routing: Of Theory and Practice
Fabian Kuhn, Roger Wattenhofer, Yan Zhang, Aaron Zollinger

R6: Broadcasting in Undirected Ad Hoc Radio Networks
Dariusz Kowalski, Andrzej Pelc

BA1: An Elegant Cluster-Based Control Mechanism for Communication Networks
Srikant Kuppa, Mansi Ramakrishnan, Srinivasan Krishnamurthy, S. Venkatesan

12:30pm - 1:50pm Lunch (provided by PODC)
1:50pm - 3:25pm Session 3 - Chair: Marcos Aguilera

R7: Split-Ordered Lists - Lock-Free Extensible Hash Tables
Ori Shalev, Nir Shavit

R8: Software Transactional Memory for Dynamic-Sized Data Structures
Maurice Herlihy, Victor Luchangco, Mark Moir, William Scherer

R9: Operation-Valency and the Cost of Coordination
Danny Hendler, Nir Shavit

BA2: Concurrent Counting is Harder than Queuing
Srikanta Tirthapura

BA3: Dynamic Group Communication
Andre Schiper

3:25pm - 3:45pm Break
3:45pm - 5:45pm Session 4 - Chair: James Aspnes

R10: Scalable and Dynamic Quorum Systems
Moni Naor, Udi Wieder

R11: Peer-to-Peer Systems for Prefix Search
Baruch Awerbuch, Christian Scheideler

R12: Routing Networks for Distributed Hash Tables
Gurmeet Singh Manku

R13: Asynchronous Resource Discovery
Ittai Abraham, Danny Dolev

BA4: An Overview of the Content-Addressable Network D2B
Pierre Fraigniaud, Philippe Gauron

BA5: Deterministic SkipNet
Nicholas J.A. Harvey, J. Ian Munro

5:45pm - 8:30pm Dinner on your own
8:30pm - 11:00pm Business Meeting and Rump Session - Meeting in Ballroom

July 15, 2003 - Tuesday

8:00am - 8:30am Breakfast (provided by PODC)
8:30am - 9:30am Invited Talk 2
Cryptography and Competition Policy -- Issues with `Trusted Computing'
Ross Anderson, University of Cambridge
9:30am - 10:20am Session 5 (Security) - Chair: Amir Herzberg

R14: An Asynchronous Protocol for Distributed Computation of RSA Inverses and its Applications
Christian Cachin

R15: Efficient Revocation and Threshold Pairing Based Cryptosystems
Benoit Libert, Jean-Jacques Quisquater

10:20am - 10:40am Break
10:40am - 12:15pm Session 6 (Security) - Chair: Gene Itkis

R16: Constructing Fair-Exchange Protocols for E-Commerce Via Distributed Computation of RSA Signatures
Jung Min Park, Edwin Chong, Howard Siegel, Indrajit Ray

R17: Oblivious Signature-Based Envelope
Ninghui Li, Wenliang Du, Dan Boneh

R18: Scalable Public-Key Tracing and Revoking
Yevgeniy Dodis, Nelly Fazio, Aggelos Kiayias, Moti Yung

BA 6: Impossibility Results for Concurrent Secure Two-Party Computation
Yehuda Lindell

BA7: A Method for Exchanging Valuable Data: How to Realize Matching Oblivious Transfer
Shin'ichiro Matsuo, Wakaha Ogata

12:15pm - 2:15pm Lunch (on your own)
2:15pm - 3:25pm Session 7 - Chair: Marcos Aguilera

R19: Distributed Consensus in the Presence of Sectional Faults
Amitanand Aiyer, Sanketh Indarapu, Srinathan Kannan, Vinod Vaikuntanathan, C. Pandu Rangan

R20: Efficient Player-Optimal Protocols for Strong and Differential Consensus
Matthias Fitzi, Juan Garay

BA8: Tight Bounds for k-Set Agreement with Limited-Scope Failure Detectors
Maurice Herlihy, Lucia Penso

BA9: Early Decision Despite General Process Omission Failures
Fabrice Le Fessant, Philippe Raipin Parvedy, Michel Raynal

3:25pm - 3:45pm Break
3:45pm - 4:45pm

Invited Talk 3
Title: TBA
Butler Lampson, Microsoft Research
4:45pm - 6:30pm Session 8 (Security) - Chair: Juan Garay

R21: Proactive Secure Message Transmission in Asynchronous Networks
Michael Backes, Christian Cachin, Reto Strobl

R22: Efficient Reliable Communication over Partially Authenticated Networks
Amos Beimel, Lior Malka

R23: Algorithms for Dynamic Multicast Key Distribution Trees
Justin Goshi, Richard Ladner

BA10: Efficient Perfect Communication over Synchronous Networks
K. Srinathan, V. Vinod, C. Pandu Rangan

BA11: Building Data Structures on Untrusted Peer-to-Peer Storage with Per-participant Logs
Benjie Chen, Robert Morris

BA12: Extending SQL Security to Derived and Distributed Data
Arnon Rosenthal, Edward Sciore

6:30pm - 7:45pm Cocktail Reception - Courtyard
7:45pm - 9:30pm Banquet (with speeches and award presentations) - Ballroom

July 16, 2003 - Wednesday

8:00am - 8:30am Breakfast (provided by PODC)
8:30am - 9:30am Invited Talk 4
Title: Simple and Fast Optimistic Protocols for Fair Electronic Exchange
Silvio Micali, Massachusetts Institute of Technology
9:30am - 10:20am Session 9 - Chair: Amir Herzberg

R24: A Work-Optimal Deterministic Algorithm for the Asynchronous Certified Write-All Problem
Grzegorz Malewicz

R25: Performing Work with Asynchronous Processors: Message-Delay-Sensitive Bounds
Dariusz Kowalski, Alex Shvartsman

10:20 - 10:40 Break
10:40am - 12:05pm Session 10 - Chair: Vassos Hadzilacos

R26: Fair Group Mutual Exclusion
Prasad Jayanti, Srdjan Petrovic, King Tan

R27: Efficient and Practical Constructions of LL/SC Variables
Prasad Jayanti, Srdjan Petrovic

R28: Adaptive and Efficient Abortable Mutual Exclusion
Prasad Jayanti

BA13: Automatic Discovery of Mutual Exclusion Algorithms
Yoah Bar-David, Gadi Taubenfeld

12:05pm - 1:25pm Lunch (provided by PODC)
1:25pm - 3:00pm Session 11 - Chair: Sergio Rajsbaum

R29: On Implementing Omega with Weak Reliability and Synchrony Assumptions
Marcos Aguilera, Carole Delporte-Gallet, Hugues Fauconnier, Sam Toueg

R30: On Using Network Attached Disks as Shared Memory
Marcos Aguilera, Burkhard Englert, Eli Gafni

R31: A Lattice-Theoretic Characterization of Safety and Liveness
Panagiotis Manolios, Richard Trefler

BA14: Branching Time Refinement
Panagiotis Manolios

BA15: Efficient Replication of Large Data Objects
Rui Fan, Nancy Lynch

3:00pm - 3:20pm Break
3:20pm - 5:10pm Session 12 - Chair: Boaz Patt-Shamir

BA16: Efficient Flooding in Power-Law Networks
Farnoush Banaei-Kashani, Cyrus Shahabi

R32: Scaling Properties of the Internet Graph
Aditya Akella, Shuchi Chawla, Arvind Kannan, Srinivasan Seshan

R33: On a Network Creation Game
Alex Fabrikant, Ankur Luthra, Elitza Maneva, Christos H. Papadimitriou, Scott Shenker

R34: Adaptive AIMD Congestion Control
Alexander Kesselman, Yishay Mansour

R35: Adapting to a Reliable Network Path
Baruch Awerbuch, Yishay Mansour

5:10pm Concluding Remarks, Conference adjourns
Sergio Rajsbaum, Program Committee Chair

Links on This Page

The links in this document should provide you with access to the fullest versions of the papers that are available. In some cases, different versions are listed. Please consult the authors' home pages (if indicated) for further information and for email address by which you might inquire for future versions or related papers.  If you find the links to be broken, please contact the authors (and not PODC).

Authors of PODC papers wishing to be listed here should send email with the appropriate URL's to Rita Tavilla (

This page is maintained by Mark Moir (