PODC 2000

July 16, 2000, Sunday

15:00 - 17:00 Tutorial I
Distributed Algorithms in TLA
Leslie Lamport, Compaq Systems Research Center
17:30 - 19:30 Reception

July 17, 2000, Monday

8:30 - 8:35 Opening Remarks
James H. Anderson, Program-Committee Chair
8:35 - 9:35 Invited Talk
Data Communications vs. Distributed Computing
Craig Partridge, BBN Technologies
9: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 Mans

Optimal Smoothing Schedules for Real-Time Streams
Yishay Mansour, Boaz Patt-Shamir, and Ofer Lapid

Average-Case Analysis of Greedy Packet Scheduling
Zvi Lotker and Boaz Patt-Shamir

Sparse Communication Networks and Efficient Routing in the Plane
Yehuda Hassin and David Peleg
Winner, Best Student Paper Award

Compact Roundtrip Routing in Directed Networks
Lenore Cowen and Christopher Wagner

12: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 Moir

Long-Lived and Adaptive Atomic Snap-Shot and Immediate Snapshot
Yehuda Afek, Gideon Stupp, and Dan Touitou

Bounds on the Shared Memory Requirements for Long-Lived and Adaptive Objects
Yehuda Afek, Pazi Boxer, and Dan Touitou

Adaptive and Efficient Mutual Exclusion
Hagit Attiya and Vita Bortnikov

15: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 Theel

Time and Message-Efficient S-Based Consensus
Fabiola Greve, Michel Hurfin, Raimundo Macêdo, and Michel Raynal

Self-Stabilization: Beyond the Token Ring Circulation
Augusto Ciuffoletti

Optimal Implementation of the Weakest Failure Detector for Solving Consensus
Mikel Larrea, Antonio Fernández, and Sergio Arévalo

Memory Consistency and Process Coordination for SPARC v8 Multiprocessors
Jalal Kawash and Lisa Higham

Deterministic Distributed Resource Discovery
Shay Kutten and David Peleg

Compact Routing with Stretch Factor of Less Than Three
Kazuo Iwama and Akinori Kawachi

Specification, Implementation and Application of Randomized Regular Registers
Hyunyoung Lee and Jennifer L. Welch

Distributed Cooperation in the Absence of Communication
Greg Malewicz, Alexander Russell, and Alex Shvartsman

Average Probe Complexity of Non-dominated Coteries
Tiko Kameda, Feng Xiao, and Malika Guerni-Mahoui

Fast Protocol Transition in A Distributed Environment
Xiaoming Liu and Robbert van Renesse

17: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-Madison
9: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érennes

The Wakeup Problem in Synchronous Broadcast Systems
Leszek Gasieniec, Andrzej Pelc, and David Peleg

Random Oracles in Constantinople: Practical Asynchronous Byzantine Agreement using Cryptography
Christian Cachin, Klaus Kursawe, and Victor Shoup

Clock Synchronization with Faults and Recoveries
Boaz Barak, Shai Halevi, Amir Herzberg, and Dalit Naor

k-Set Agreement with Limited Accuracy Failure Detectors
Achour Mostéfaoui and Michel Raynal

11: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 Ramachandran

On the Interconnection of Causal Memory Systems
Antonio Fernández, Ernesto Jiménez, and Vicente Cholvi

Distributed Reconfiguration of Metamorphic Robot Chains
Jennifer E. Walter, Jennifer L. Welch, and Nancy M. Amato

1/k Phase Stamping for Continuous Shared Data
Sumeer Bhola and Mustaque Ahamad

15: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 & Inktomi
9: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 Seitz

High Performance Adaptive Middleware for CORBA-Based Systems
E-Kai Shen, Shikharesh Majumdar, and Istabrak Abdul-Fatah

Efficient Atomic Broadcast Using Deterministic Merge
Marcos Kawazoe Aguilera and Robert E. Strom

Achieving Scalability and Expressiveness in an Internet-Scale Event Notification Service
Antonio Carzaniga, David S. Rosenblum, and Alexander L. Wolf

X-Ability: A Theory of Replication
Svend Frølund and Rachid Guerraoui

11: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 Singh

Resettable Vector Clocks
Anish Arora, Sandeep Kulkarni, and Murat Demirbas

Debugging Distributed Programs Using Controlled Re-execution
Neeraj Mittal and Vijay K. Garg

Self-stabilizing Token Circulation on Asynchronous Uniform Unidirectional Rings
Laurent Rosaz

15: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 Kameda

Indulgent Algorithms
Rachid Guerraoui

Fast Deterministic Consensus in a Noisy Environment
James Aspnes

Stability of Long-lived Consensus
Shlomi Dolev and Sergio Rajsbaum

Toward a Theory of Maximally Concurrent Programs
Rajeev Joshi and Jayadev Misra

17:50 Conference adjourns

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 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 (

This page maintained by Gil Neiger.

Last modified: July 21, 2000