Schedule for PODC '99

Monday, May 3

6:30pm - 8:00pm RECEPTION

Tuesday, May 4

Session 1

8:30amOptimal and Efficient Clock Synchronization Under Drifting Clocks

Rafail Ostrovsky (Bellcore) and Boaz Patt-Shamir (Tel-Aviv U.)

8:55amAnalysis of Timing-Based Mutual Exclusion with Random Times

Eli Gafni (UCLA) and Michael Mitzenmacher (Harvard U.)

9:20amA Faster Distributed Algorithm for Computing Maximal Matchings Deterministically

Michal Hanckowiak (Adam Mickiewicz U.), Michal Karonski (Adam Mickiewicz U. and Emory U.) and Alessandro Panconesi (U. of Bologna)

9:45am- BREAK

Session 2

10:10amRollback-Dependency Trackability: Visible Characterizations

Roberto Baldoni (U. di Roma), Jean-Michel Helary (IRISA) and Michel Raynal (IRISA)

10:35amOptional Locking Integrated with Operational Transformation in Distributed Real-Time Group Editors

Chengzheng Sun (Griffith U.) and Rok Sosic (Griffith U.)

11:00amMatching Events in a Content-based Subscription System

Marcos K. Aguilera (Cornell U.), Robert E. Strom (IBM T.J. Watson Research Center), Daniel C. Sturman (IBM T.J. Watson Research Center), Mark Astley (U. of Illinois at Urbana-Champaign) and Tushar D. Chandra (IBM T.J. Watson Research Center)

11:30am- PLENARY TALK

12:30pm- LUNCH

Session 3

2:25pmLiveness-preserving Simulation Relations

Paul C. Attie (Florida International U.)

2:50pmA Knowledge-Theoretic Analysis of Uniform Distributed Coordination and Failure Detectors

Joseph Y. Halpern (Cornell U.) and Aleta Ricciardi (Bell Labs)

3:15pmFlash Mixing

Markus Jakobsson (Bell Labs)

3:40pm- BREAK

Session 4

4:10pmLong-Lived Renaming Made Adaptive

Yehuda Afek (Tel-Aviv U.), Hagit Attiya (Technion), Arie Fouren (Technion), Gideon Stupp (Tel-Aviv U.) and Dan Touitou (IDC)

4:35pmFast, Wait-Free (2k-1)-Renaming

Yehuda Afek (Tel-Aviv U.) and Michael Merritt (AT&T Labs)

5:30pm- POSTER SESSION

Brief Announcement: A Design of a Protocol for Detecting an Agent Clone in Mobile Agent Systems and its Correctness Proof

Jusung Baek (Mirae Co. SoftForum), R. S. Ramakrishna (KJIST) and Donk-Ik Lee (KJIST)

Brief Announcement: Mutable Checkpoints: A New Checkpointing Approach for Mobile Computing Systems

Guohong Cao (Ohio State U.) and Mukesh Singhal (Ohio State U.)

Brief Announcement: Delay-Optimal Quorum-Based Mutual Exclusion for Distributed Systems

Guohong Cao (Ohio State U.), Mukesh Singhal (Ohio State U.) and Naphtali Rishe (Florida International U.)

Brief Announcement: The HiMAT Model for Mobile Agent Applications

Marco Cremonini (U. di Bologna), Andrea Omicini (U. di Bologna) and Franco Zambonelli (U. di Modena e Reggio E.)

Brief Announcement: The Sound of Silence --- Guessing Games for Saving Energy in Mobile Environment

Shlomi Dolev (Ben-Gurion U.), Ephraim Korach (Ben-Gurion U.) and Dmitry Yukelson (Ben-Gurion U.)

Brief Announcement: Fundamental Distributed Protocols in Mobile Networks

Kostas P. Hatzis (Computer Technology Institute and Patras U.), George P. Pentaris (Computer Technology Institute and Patras U.), Paul G. Spirakis (Computer Technology Institute and Patras U.), Vasilis T. Tampakis (Computer Technology Institute and TEI) and Richard B. Tan (U. Utrecht)

Brief Announcement: External Logging on a Logical Ring

Jerry James (U. of California, Santa Barbara) and Ambuj K. Singh (U. of California, Santa Barbara)

Brief Announcement: A Dynamic Self-Stabilizing Algorithm for Finding Strongly Connected Components

Mehmet Hakan Karaata (Kuwait U.) and Fawaz Al-Anzi (Kuwait U.)

Brief Announcement: Two Classes of Communication Patterns

Ajay D. Kshemkalyani (U. of Illinois at Chicago) and Mukesh Singhal (National Science Foundation)

Brief Announcement: Dynamically Configurable Distributed Objects

Michael J. Lewis (U. of Virginia) and Andrew S. Grimshaw (U. of Virginia)

Brief Announcement: Optimal, Distributed Decision-Making: The Case of No Communication

Marios Mavronicolas (U. of Connecticut) and Paul Spirakis (U. of Patras)

Brief Announcement: Using CSP to Derive a Sequentially Consistent DSM System

E. Perez Cortes (U. Autonoma Metropolitana), G. Roman Alonso (U. Autonoma Metropolitana) and H. Ruiz Barradas (U. Autonoma Metropolitana)

Brief Announcement: Properties of a Family of Booster Types

Gary L. Peterson (Spelman College)

Brief Announcement: Maintenance of a Spanning Tree in Dynamic Network

Avner Porat (Technion)

Brief Announcement: Lower and Upper Bounds for Attacks on Authentication Protocols

Scott D. Stoller (Indiana U.)

Brief Announcement: A Design Methodology for Mobile Distributed Applications Based on UNITY Formalism and Communication-Closed Layering

Camelia Zlatea (Illinois Institute of Technology) and Tzilla Elrad (Illinois Institute of Technology)

6:00pm - 7:00pm MIXER

8:00pm - 11:00pm BUSINESS MEETING

Wednesday, May 5

Session 5

8:30amScalable Concurrent Priority Queue Algorithms

Nir Shavit (Tel-Aviv U. and MIT) and Asaph Zemach (Tel-Aviv U. and Tera Computer Co.)

8:55amWait-Free Synchronization in Multiprogrammed Systems: Integrating Priority-Based and Quantum-Based Scheduling

James H. Anderson (U. of North Carolina) and Mark Moir (U. of Pittsburgh)

9:20amSequentially Consistent versus Linearizable Counting Networks

Marios Mavronicolas (U. of Connecticut), Michael Merritt (AT&T Labs) and Gadi Taubenfeld (Open U.)

9:45am- BREAK

Session 6

10:10amDecentralized Replicated-Object Protocols

Peter J. Keleher (U. of Maryland)

10:35amLOTEC: A Simple DSM Consistency Protocol for Nested Object Transactions

Peter Graham (U. of Manitoba) and Yahong Sui (U. of Manitoba)

11:00amTimed Consistency for Shared Distributed Objects

Francisco J. Torres-Rojas (Georgia Tech), Mustaque Ahamad (Georgia Tech) and Michel Raynal (IRISA)

11:30am- PLENARY TALK

12:30pm- LUNCH

Session 7

2:25pmComparison of Initial Conditions for Distributed Algorithms on Anonymous Networks

Naoshi Sakamoto (Tokyo Institute of Technology)

2:50pmComputing Anonymously with Arbitrary Knowledge

Paolo Boldi (U. di Milano) and Sebastiano Vigna (U. di Milano)

3:15pmBackward Consistency and Sense of Direction in Advanced Distributed Systems

Paola Flocchini (U. du Quebec a Hull), Alessandro Roncato (U. di Venezia) and Nicola Santoro (Carleton U.)

3:40pm- BREAK

Session 8

4:10pmMemory Space Requirements for Self-Stabilizing Leader Election Protocols

Joffroy Beauquier (U. de Paris-Sud), Maria Gradinariu (U. de Paris-Sud) and Colette Johnen (U. de Paris-Sud)

4:35pmOptimal Reactive k-Stabilization

Joffroy Beauquier (U. de Paris-Sud), Christophe Genolini (U. de Paris-Sud) and Shay Kutten (Technion)

6:00pm - 7:00pm MIXER

Thursday, May 6

Session 9

8:30amA Simple Local-Spin Group Mutual Exclusion Algorithm

Patrick Keane (U. of Pittsburgh) and Mark Moir (U. of Pittsburgh)

8:55amResource Discovery in Distributed Networks

Mor Harchol-Balter (MIT), Tom Leighton (MIT) and Daniel Lewin (MIT)

9:20amThe Complexity of End-to-End Communication in Memoryless Networks

Micah Adler (U. of Toronto) and Faith Fich (U. of Toronto)

9:45am- BREAK

Session 10

10:10amFast Set Agreement in the Presence of Timing Uncertainty

Dimitris Michailidis (Brown U.)

10:35amOn k-set Consensus Problems in Asynchronous Systems

Roberto DePrisco (MIT), Dahlia Malkhi (AT&T Labs) and Michael K. Reiter (Bell Labs)

11:30am- PLENARY TALK