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.
| 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 |
| 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
|
| 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
R5: Geometric Ad-Hoc Routing: Of Theory and Practice
R6: Broadcasting in Undirected Ad Hoc Radio Networks
BA1: An Elegant Cluster-Based Control Mechanism for Communication Networks
|
| 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
R9:
Operation-Valency and the Cost of Coordination
BA2: Concurrent Counting is Harder than Queuing
BA3:
Dynamic Group Communication
|
| 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
R12:
Routing Networks for Distributed Hash Tables
R13: Asynchronous Resource Discovery
BA4: An Overview of the Content-Addressable Network D2B
BA5: Deterministic SkipNet
|
| 5:45pm - 8:30pm | Dinner on your own |
| 8:30pm - 11:00pm | Business Meeting and Rump Session - Meeting in Ballroom |
| 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
|
| 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
R18:
Scalable Public-Key Tracing and Revoking
BA 6: Impossibility Results for Concurrent Secure Two-Party Computation
BA7:
A Method for Exchanging Valuable Data: How to Realize Matching
Oblivious Transfer
|
| 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
BA8: Tight Bounds for k-Set Agreement with Limited-Scope Failure Detectors
BA9: Early Decision Despite General Process Omission Failures
|
| 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
R23: Algorithms for Dynamic Multicast Key Distribution Trees
BA10: Efficient Perfect Communication over Synchronous Networks
BA11: Building Data Structures on Untrusted Peer-to-Peer Storage with Per-participant Logs
BA12: Extending SQL Security to Derived and Distributed Data
|
| 6:30pm - 7:45pm | Cocktail Reception - Courtyard |
| 7:45pm - 9:30pm | Banquet (with speeches and award presentations) - Ballroom |
| 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
|
| 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
R28: Adaptive and Efficient Abortable Mutual Exclusion
BA13:
Automatic Discovery of Mutual Exclusion Algorithms
|
| 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
R31:
A Lattice-Theoretic Characterization of Safety and Liveness
BA14:
Branching Time Refinement
BA15: Efficient Replication of Large Data Objects
|
| 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
R33: On a Network Creation Game
R34:
Adaptive AIMD Congestion Control
R35: Adapting to a Reliable Network Path
|
| 5:10pm | Concluding Remarks, Conference adjourns
Sergio Rajsbaum, Program Committee Chair |
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 (Rita.Tavilla@sun.com).