July 16, 2000, Sunday
15:00 - 17:00 Tutorial I
Distributed Algorithms in TLA
Leslie Lamport, Compaq Systems Research Center17:30 - 19:30 Reception July 17, 2000, Monday
8:30 - 8:35 Opening Remarks
James H. Anderson, Program-Committee Chair8:35 - 9:35 Invited Talk
Data Communications vs. Distributed Computing
Craig Partridge, BBN Technologies9:35 - 9:55 Break 9:55 - 12:00 Session R1 (Chair: Injong Rhee) Interval Routing Schemes allow Broadcasting with Linear Message-Complexity
Pierre Fraigniaud, Cyril Gavoille, and Bernard MansOptimal Smoothing Schedules for Real-Time Streams
Yishay Mansour, Boaz Patt-Shamir, and Ofer LapidAverage-Case Analysis of Greedy Packet Scheduling
Zvi Lotker and Boaz Patt-ShamirSparse Communication Networks and Efficient Routing in the Plane
Yehuda Hassin and David Peleg
Winner, Best Student Paper AwardCompact Roundtrip Routing in Directed Networks
Lenore Cowen and Christopher Wagner12:00 - 13:45 Lunch (PODC-hosted, in hotel) 13:45 - 15:25 Session R2 (Chair: Maurice Herlihy) Laziness Pays! Using Lazy Synchronization Mechanisms to Improve Non-Blocking Constructions
Mark MoirLong-Lived and Adaptive Atomic Snap-Shot and Immediate Snapshot
Yehuda Afek, Gideon Stupp, and Dan TouitouBounds on the Shared Memory Requirements for Long-Lived and Adaptive Objects
Yehuda Afek, Pazi Boxer, and Dan TouitouAdaptive and Efficient Mutual Exclusion
Hagit Attiya and Vita Bortnikov15:25 - 15:45 Break 15:45 - 17:35 Session BA1 (Chair: Mark Moir) A Verification Technique for Self-Stabilizing Algorithms based on Ljapunov's "Second Method"
Oliver TheelTime and Message-Efficient S-Based Consensus
Fabiola Greve, Michel Hurfin, Raimundo Macêdo, and Michel RaynalSelf-Stabilization: Beyond the Token Ring Circulation
Augusto CiuffolettiOptimal Implementation of the Weakest Failure Detector for Solving Consensus
Mikel Larrea, Antonio Fernández, and Sergio ArévaloMemory Consistency and Process Coordination for SPARC v8 Multiprocessors
Jalal Kawash and Lisa HighamDeterministic Distributed Resource Discovery
Shay Kutten and David PelegCompact Routing with Stretch Factor of Less Than Three
Kazuo Iwama and Akinori KawachiSpecification, Implementation and Application of Randomized Regular Registers
Hyunyoung Lee and Jennifer L. WelchDistributed Cooperation in the Absence of Communication
Greg Malewicz, Alexander Russell, and Alex ShvartsmanAverage Probe Complexity of Non-dominated Coteries
Tiko Kameda, Feng Xiao, and Malika Guerni-MahouiFast Protocol Transition in A Distributed Environment
Xiaoming Liu and Robbert van Renesse17:35 - 20:30 Dinner on your own 20:30 - 23:00 Business Meeting, PODC Influential Paper Award Presentation, and Rump Session July 18, 2000, Tuesday
8:30 - 9:30 Invited Talk
How Computer Architecture Trends May Affect Future Distributed Systems: From InfiniBand Clusters to Inter-Processor Speculation
Mark D. Hill, University of Wisconsin-Madison9:30 - 9:50 Break 9:50 - 11:55 Session R3 (Chair: Faith Fich) Assigning labels in unknown anonymous networks
Pierre Fraigniaud, Andrzej Pelc, David Peleg, and Stepháne PérennesThe Wakeup Problem in Synchronous Broadcast Systems
Leszek Gasieniec, Andrzej Pelc, and David PelegRandom Oracles in Constantinople: Practical Asynchronous Byzantine Agreement using Cryptography
Christian Cachin, Klaus Kursawe, and Victor ShoupClock Synchronization with Faults and Recoveries
Boaz Barak, Shai Halevi, Amir Herzberg, and Dalit Naork-Set Agreement with Limited Accuracy Failure Detectors
Achour Mostéfaoui and Michel Raynal11:55 - 13:45 Lunch on your own 13:45 - 15:25 Session R4 (Chair: Alex Shvartsman) Garbage Collection of Timestamped Data in Stampede
Rishiyur S. Nikhil and Umakishore RamachandranOn the Interconnection of Causal Memory Systems
Antonio Fernández, Ernesto Jiménez, and Vicente CholviDistributed Reconfiguration of Metamorphic Robot Chains
Jennifer E. Walter, Jennifer L. Welch, and Nancy M. Amato1/k Phase Stamping for Continuous Shared Data
Sumeer Bhola and Mustaque Ahamad15:25 - 15:55 Break 15:55 - 17:55 Tutorial II
A Middleware Overview: Goals, Research Issues, and Coded Examples
Michael Ogg, Synaptus, Inc.18:30 - 21:00 Banquet July 19, 2000, Wednesday
8:30 - 9:30 Invited Talk
Towards Robust Distributed Systems
Eric A. Brewer, University of California, Berkeley & Inktomi9:30 - 9:50 Break 9:50 - 11:55 Session R5 (Chair: Keith Marzullo) P2: A Generic Proxy Platform for Wireless Access and Mobility in CORBA
Michael Knapp, Rainer Ruggaber, and Jochen SeitzHigh Performance Adaptive Middleware for CORBA-Based Systems
E-Kai Shen, Shikharesh Majumdar, and Istabrak Abdul-FatahEfficient Atomic Broadcast Using Deterministic Merge
Marcos Kawazoe Aguilera and Robert E. StromAchieving Scalability and Expressiveness in an Internet-Scale Event Notification Service
Antonio Carzaniga, David S. Rosenblum, and Alexander L. WolfX-Ability: A Theory of Replication
Svend Frølund and Rachid Guerraoui11:55 - 13:45 Joint PODC-Middleware Lunch (in hotel) 13:45 - 15:25 Session R6 (Chair: Rida A. Bazzi) Stable and Fault-Tolerant Object Replication
Gregory Johnson and Ambuj SinghResettable Vector Clocks
Anish Arora, Sandeep Kulkarni, and Murat DemirbasDebugging Distributed Programs Using Controlled Re-execution
Neeraj Mittal and Vijay K. GargSelf-stabilizing Token Circulation on Asynchronous Uniform Unidirectional Rings
Laurent Rosaz15:25 - 15:45 Break 15:45 - 17:50 Session R7 (Chair: Alex Shvartsman) Efficient Generation of All Regular Non-Dominated Coteries
Kazuhisa Makino and Tiko KamedaIndulgent Algorithms
Rachid GuerraouiFast Deterministic Consensus in a Noisy Environment
James AspnesStability of Long-lived Consensus
Shlomi Dolev and Sergio RajsbaumToward a Theory of Maximally Concurrent Programs
Rajeev Joshi and Jayadev Misra17:50 Conference adjourns
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 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 Gil Neiger (gilATacm.org).
Last modified: July 21, 2000