PROGRAM FOR PODC 2001

The following is the program for PODC 2001.
August 26, 2001, Sunday

17:00 - 19:00 Reception

19:00 - 19:10 Lamport Celebration Opening Remarks
Cynthia Dwork, Lamport Celebration Chair

19:10 - 20:10 Lamport Celebration Lecture 1
Lamport on Mutual Exclusion: 27 Years of Planting Seeds (postscript, PDF)
James Anderson, U. of North Carolina at Chapel Hill

August 27, 2001, Monday

8:30 - 8:35 Opening Remarks
Nir Shavit, Program Committee Chair

8:35 - 9:35 Lamport Celebration Lecture 2
The ABCD's of Paxos
Butler Lampson, Microsoft

9:35 - 9:55 Break

9:55 - 12:00 Session R1 (Chair: Mark Tuttle)
An Efficient Distributed Algorithm for Constructing Small Dominating Sets
Lujun Jia, Rajmohan Rajaraman, and Torsten Suel
Winner, Best Student Paper Award
Restoration by Path Concatenation: Fast Recovery of MPLS Paths
Anat Bremler-Barr, Yehuda Afek, Haim Kaplan, Edith Cohen, and Michael Merritt
Computing Almost Shortest Paths
Michael Elkin
Distributed MST for Constant Diameter Graphs
Zvi Lotker, Boaz Patt-Shamir, and David Peleg
String Realizers of Posets with Applications to Distributed Computing
Vijay K. Garg and Chakarat Skawratananond

12:00 - 13:45 Lunch (hosted by PODC)

13:45 - 14:45 Lamport Celebration Lecture 3
Sticks and Stones: A Coding Scheme for Parameterized Verification
Amir Pnueli, The Weizmann Institute

14:45 - 15:45 Lamport Celebration Lecture 4
Leslie Lamport's Properties and Actions
Martin Abadi, InterTrust

15:45 - 16:05 Break

16:05 - 17:20 Session R2 (Chair: Dave Detlefs)
On the Generalized Dining Philosophers Problem
Oltea Mihaela Herescu and Catuscia Palamidessi
An Improved Lower Bound for the Time Complexity of Mutual Exclusion (postscript, PDF)
James H. Anderson and Yong-Jik Kim
A Note on Group Mutual Exclusion
Vassos Hadzilacos

17:20 - 20:30 Dinner on your own

20:30 - 23:00 Business Meeting, PODC Influential Paper Award Presentation, and Rump Session

August 28, 2001, Tuesday

8:30 - 9:30 Lamport Celebration Lecture 5
Implementing Atomic Objects in a Dynamic Environment
Nancy Lynch, MIT

9:30 - 9:50 Break

9:50 - 11:55 Session R3 (Chair: Michel Raynal)
Nearly Optimal Perfectly-Periodic Schedules
Amotz Bar-Noy, Aviv Nisgav, and Boaz Patt-Shamir
The Do-All Problem in Broadcast Networks
Bogdan S. Chlebus, Dariusz R. Kowalski, Andrzej Lingas
Competitive Concurrent Distributed Queuing
Maurice Herlihy, Srikanta Tirthapura, and Roger Wattenhofer
Bandwidth Constrained Placement in a WAN (postscript, PDF)
Arun Venkataramani, Phoebe Wiedmann, and Mike Dahlin
Compressed Bloom Filters (updated version)
Michael Mitzenmacher

11:55 - 13:45 Lunch (on your own)

13:45 - 15:25 Session R4 (Chair: Marios Mavronicolas)
A Hierarchy of Conditions for Consensus Solvability
Achour Mostefaoui, Sergio Rajsbaum, Michel Raynal, and Matthieu Roy
The Concurrency Hierarchy, and Algorithms for Unbounded Concurrency
Eli Gafni, Michael Merritt, and Gadi Taubenfeld
On Scalable and Efficient Distributed Failure Detectors (postscript, PDF)
Indranil Gupta, Tushar D. Chandra, and German S. Goldszmidt
Average Probe Complexity in Quorum Systems
Yehuda Hassin and David Peleg

15:25 - 15:45 Break

15:45 - 16:45 Lamport Celebration Lecture 6
The Latex Legacy 2.09 And All That
Chris Rowley, Open University UK

16:45 - 17:45 Brief Announcement Session (Chair: Lisa Higham)
Brief Announcement: Optimal Scheduling for Disconnected Cooperation
Grzegorz G. Malewicz, Alexander Russell, and Alex A. Shvartsman
Brief Announcement: Adding Networks
Panagiota Fatourou and Maurice Herlihy
Brief Announcement: Randomized Shared Queues
Hyunyoung Lee and Jennifer L. Welch
Brief Announcement: Dynamic Input/Output Automata: a Formal Model for Dynamic Systems
Paul Attie and Nancy Lynch
Brief Announcement: A Framework for Semantic Reasoning about Byzantine Quorum Systems
Evelyn Pierce and Lorenzo Alvisi
Brief Announcement: An Efficient Communication Strategy for Ad-hoc Mobile Networks
Ioannis Chatzigiannakis, Sotiris Nikoletseas, and Paul Spirakis

18:30 - 21:00 Banquet

August 29, 2001, Wednesday

8:30 - 9:30 Lamport Celebration Lecture 7
On Beyond Registers: Wait-free Readable Objects
Maurice Herlihy, Brown U.

9:30 - 9:50 Break

9:50 - 11:05 Session R5 (Chair: Liuba Shrira)
Lock-Free Reference Counting
David Detlefs, Paul Martin, Mark Moir, and Guy Steele
Detecting Distributed Cycles of Garbage in Large-Scale Systems
Fabrice Le Fessant
The IceCube Approach to the Reconciliation of Divergent Replicas
Anne-Marie Kermarrec, Antony Rowstron, Marc Shapiro, and Peter Druschel

11:05 - 11:15 Short Break

11:15 - 12:30 Session R6 (Chair: Ran Canetti)
Exploiting Event Stream Interpretation in Publish-Subscribe Systems
Yuanyuan Zhao and Rob Strom
Replicated Condition Monitoring
Yongqiang Huang
Computing Property-Preserving Behavior Abstractions from Trace Reductions
Simon St James and Ulrich Ultes-Nitsche

12:30 - 14:00 Joint PODC-POMC Lunch

14:00 - 15:15 Session R7 (Chair: Idit Keidar)
Reliability and Performance of Hierarchical RAID with Multiple Controllers
Sung Hoon Baek, Bong Wan Kim, Eui Joung Joung, and Chong Won Park
Distributed Multi-Broadcast in Unknown Radio Networks
Andrea E. F. Clementi, Angelo Monti, and Riccardo Silvestri
Analysis of a Cone-Based Distributed Topology Control Algorithm for
Wireless Multi-hop Networks
Li Li, Joseph Halpern, Victor Bahl, Yi-Min Wang, and Roger Wattenhofer

15:15 - 15:35 Break

15:35 - 16:50 Session R8 (Chair: Eric Ruppert)
Practical Multi-Candidate Election System
Olivier Baudron, Pierre-Alain Fouque, David Pointcheval, Guillaume Poupard, and Jacques Stern
An Optimally Robust Hybrid Mix Network
Markus Jakobsson and Ari Juels
Selective Private Function Evaluation with Applications to Private Statistics
Ran Canetti, Yuval Ishai, Ravi Kumar, Michael Reiter, Ronitt Rubinfeld, and Rebecca Wright

16:50 Concluding Remarks
Nir Shavit, Program Committee Chair

17:00 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 (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 Gil Neiger (gil AT acm dot org).

This page maintained by Gil Neiger.

Last modified: September 3, 2001

17:00 - 19:00	Reception
19:00 - 19:10	Lamport Celebration Opening Remarks Cynthia Dwork, Lamport Celebration Chair
19:10 - 20:10	Lamport Celebration Lecture 1 Lamport on Mutual Exclusion: 27 Years of Planting Seeds (postscript, PDF) James Anderson, U. of North Carolina at Chapel Hill

8:30 - 8:35	Opening Remarks Nir Shavit, Program Committee Chair
8:35 - 9:35	Lamport Celebration Lecture 2 The ABCD's of Paxos Butler Lampson, Microsoft
9:35 - 9:55	Break
9:55 - 12:00	Session R1 (Chair: Mark Tuttle) An Efficient Distributed Algorithm for Constructing Small Dominating Sets Lujun Jia, Rajmohan Rajaraman, and Torsten Suel Winner, Best Student Paper Award Restoration by Path Concatenation: Fast Recovery of MPLS Paths Anat Bremler-Barr, Yehuda Afek, Haim Kaplan, Edith Cohen, and Michael Merritt Computing Almost Shortest Paths Michael Elkin Distributed MST for Constant Diameter Graphs Zvi Lotker, Boaz Patt-Shamir, and David Peleg String Realizers of Posets with Applications to Distributed Computing Vijay K. Garg and Chakarat Skawratananond
12:00 - 13:45	Lunch (hosted by PODC)
13:45 - 14:45	Lamport Celebration Lecture 3 Sticks and Stones: A Coding Scheme for Parameterized Verification Amir Pnueli, The Weizmann Institute
14:45 - 15:45	Lamport Celebration Lecture 4 Leslie Lamport's Properties and Actions Martin Abadi, InterTrust
15:45 - 16:05	Break
16:05 - 17:20	Session R2 (Chair: Dave Detlefs) On the Generalized Dining Philosophers Problem Oltea Mihaela Herescu and Catuscia Palamidessi An Improved Lower Bound for the Time Complexity of Mutual Exclusion (postscript, PDF) James H. Anderson and Yong-Jik Kim A Note on Group Mutual Exclusion Vassos Hadzilacos
17:20 - 20:30	Dinner on your own
20:30 - 23:00	Business Meeting, PODC Influential Paper Award Presentation, and Rump Session

8:30 - 9:30	Lamport Celebration Lecture 5 Implementing Atomic Objects in a Dynamic Environment Nancy Lynch, MIT
9:30 - 9:50	Break
9:50 - 11:55	Session R3 (Chair: Michel Raynal) Nearly Optimal Perfectly-Periodic Schedules Amotz Bar-Noy, Aviv Nisgav, and Boaz Patt-Shamir The Do-All Problem in Broadcast Networks Bogdan S. Chlebus, Dariusz R. Kowalski, Andrzej Lingas Competitive Concurrent Distributed Queuing Maurice Herlihy, Srikanta Tirthapura, and Roger Wattenhofer Bandwidth Constrained Placement in a WAN (postscript, PDF) Arun Venkataramani, Phoebe Wiedmann, and Mike Dahlin Compressed Bloom Filters (updated version) Michael Mitzenmacher
11:55 - 13:45	Lunch (on your own)
13:45 - 15:25	Session R4 (Chair: Marios Mavronicolas) A Hierarchy of Conditions for Consensus Solvability Achour Mostefaoui, Sergio Rajsbaum, Michel Raynal, and Matthieu Roy The Concurrency Hierarchy, and Algorithms for Unbounded Concurrency Eli Gafni, Michael Merritt, and Gadi Taubenfeld On Scalable and Efficient Distributed Failure Detectors (postscript, PDF) Indranil Gupta, Tushar D. Chandra, and German S. Goldszmidt Average Probe Complexity in Quorum Systems Yehuda Hassin and David Peleg
15:25 - 15:45	Break
15:45 - 16:45	Lamport Celebration Lecture 6 The Latex Legacy 2.09 And All That Chris Rowley, Open University UK
16:45 - 17:45	Brief Announcement Session (Chair: Lisa Higham) Brief Announcement: Optimal Scheduling for Disconnected Cooperation Grzegorz G. Malewicz, Alexander Russell, and Alex A. Shvartsman Brief Announcement: Adding Networks Panagiota Fatourou and Maurice Herlihy Brief Announcement: Randomized Shared Queues Hyunyoung Lee and Jennifer L. Welch Brief Announcement: Dynamic Input/Output Automata: a Formal Model for Dynamic Systems Paul Attie and Nancy Lynch Brief Announcement: A Framework for Semantic Reasoning about Byzantine Quorum Systems Evelyn Pierce and Lorenzo Alvisi Brief Announcement: An Efficient Communication Strategy for Ad-hoc Mobile Networks Ioannis Chatzigiannakis, Sotiris Nikoletseas, and Paul Spirakis
18:30 - 21:00	Banquet

8:30 - 9:30	Lamport Celebration Lecture 7 On Beyond Registers: Wait-free Readable Objects Maurice Herlihy, Brown U.
9:30 - 9:50	Break
9:50 - 11:05	Session R5 (Chair: Liuba Shrira) Lock-Free Reference Counting David Detlefs, Paul Martin, Mark Moir, and Guy Steele Detecting Distributed Cycles of Garbage in Large-Scale Systems Fabrice Le Fessant The IceCube Approach to the Reconciliation of Divergent Replicas Anne-Marie Kermarrec, Antony Rowstron, Marc Shapiro, and Peter Druschel
11:05 - 11:15	Short Break
11:15 - 12:30	Session R6 (Chair: Ran Canetti) Exploiting Event Stream Interpretation in Publish-Subscribe Systems Yuanyuan Zhao and Rob Strom Replicated Condition Monitoring Yongqiang Huang Computing Property-Preserving Behavior Abstractions from Trace Reductions Simon St James and Ulrich Ultes-Nitsche
12:30 - 14:00	Joint PODC-POMC Lunch
14:00 - 15:15	Session R7 (Chair: Idit Keidar) Reliability and Performance of Hierarchical RAID with Multiple Controllers Sung Hoon Baek, Bong Wan Kim, Eui Joung Joung, and Chong Won Park Distributed Multi-Broadcast in Unknown Radio Networks Andrea E. F. Clementi, Angelo Monti, and Riccardo Silvestri Analysis of a Cone-Based Distributed Topology Control Algorithm for Wireless Multi-hop Networks Li Li, Joseph Halpern, Victor Bahl, Yi-Min Wang, and Roger Wattenhofer
15:15 - 15:35	Break
15:35 - 16:50	Session R8 (Chair: Eric Ruppert) Practical Multi-Candidate Election System Olivier Baudron, Pierre-Alain Fouque, David Pointcheval, Guillaume Poupard, and Jacques Stern An Optimally Robust Hybrid Mix Network Markus Jakobsson and Ari Juels Selective Private Function Evaluation with Applications to Private Statistics Ran Canetti, Yuval Ishai, Ravi Kumar, Michael Reiter, Ronitt Rubinfeld, and Rebecca Wright
16:50	Concluding Remarks Nir Shavit, Program Committee Chair
17:00	Conference adjourns