• 
  James E. Burns, Yoram Moses (Eds.): Proceedings of the Fifteenth Annual ACM Symposium on Principles of Distributed Computing, Philadelphia, Pennsylvania, USA, May 23-26, 1996. ACM 1996 ISBN 0-89791-800-2

Invited Speakers

• 
  Mahadev Satyanarayanan: Fundamental Challenges in Mobile Computing. 1-7
• 
  J. D. Tygar: Atomicity in Electronic Commerce. 8-26

Session 1

• 
  Shlomi Dolev, Mohamed G. Gouda, Marco Schneider: Memory Requirements for Silent Stabilization (Extended Abstract). 27-34
• 
  Adam M. Costello, George Varghese: Self-Stabilization by Window Washing. 35-44
• 
  Sukumar Ghosh, Arobinda Gupta, Ted Herman, Sriram V. Pemmaraju: Fault-Containing Self-Stabilizing Algorithms. 45-54
• 
  Roberto Baldoni, Jean-Michel Hélary, Michel Raynal: About State Recording in Asynchronous Computations (Abstract). 55
• 
  Michael Goldweber, Donald B. Johnson: Minimizing Access Costs in Replicated Distributed Syste (Abstract). 56
• 
  Nancy A. Lynch, Sergio Rajsbaum: On the Borowsky-Gafni Simulation Algorithm (Abstract). 57

Session 2

Joint ISCA/PODC Panel and Discussion

Session 3

• 
  Lorenzo Alvisi, Keith Marzullo: Trade-Offs in Implementing Optimal Message Logging Protocols. 58-67
• 
  Idit Keidar, Danny Dolev: Efficient Message Ordering in Dynamic Networks. 68-76
• 
  Injong Rhee, Chi-Yung Lee: An Efficient Recovery-Based Spin Lock Protocol for Preemptive Shared Memory Multiprocessors. 77-86
• 
  Ajay D. Kshemkalyani, Mukesh Singhal: An Optimal Algorithm for Generalized Causal Message Ordering (Abstract). 87
• 
  Venkatesh V. Murty, Vijay K. Garg: Characterization of Message Ordering Specifications and Protocols (Abstract). 88
• 
  Roberto Baldoni, Ravi Prakash, Michel Raynal, Mukesh Singhal: Efficient Delta-Causal Broadcasting of Multimedia Applications (Abstract). 89
• 
  Jeremy B. Sussman, Keith Marzullo: Comparing Primary-Backup and State Machines for Crash Failures (Abstract). 90

Session 4

• 
  Wil Janssen: Refining Knowledge Oriented Actions to Layered Implementations. 91-100
• 
  Nils Klarlund, Mogens Nielsen, Kim Sunesen: Automated Logical Verification Based on Trace Abstractions. 101-110
• 
  Paul C. Attie, E. Allen Emerson: Synthesis of Concurrent Systems for an Atomic Read / Atomic Write Model of Computation (Extended Abstract). 111-120
• 
  Evelyn Tumlin Pierce: Synthesis of Distributed Control Systems (Abstract). 121
• 
  Sandeep K. Shukla, Harry B. Hunt III, Daniel J. Rosenkrantz, S. S. Ravi, Richard Edwin Stearns: I/O Automata Based Verification of Finite State Distributed Systems: Complexity Issues (Abstract). 122
• 
  Dominique Ambroise, Brigitte Rozoy: Using Events Structures for the Efficient Analysis of State Graphs (Abstract). 123
• 
  John L. Bruno, Phillip B. Gibbons, Steven Phillips: Testing Concurrent Data Structures (Abstract). 124

Session 5

• 
  Cyril Gavoille, Stephane Perennes: Memory Requirements for Routing in Distributed Networks (Extended Abstract). 125-133
• 
  Harry Buhrman, Jaap-Henk Hoepman, Paul M. B. Vitányi: Optimal Routing Tables. 134-142
• 
  James Aspnes, William Hurwood: Spreading Rumors Rapidly Despite and Adversary. 143-151
• 
  Mark Moir, Juan A. Garay: Fast, Long-Lived Renaming Improved and Simplified (Abstract). 152
• 
  Evangelos Kranakis, Danny Krizanc, Andrzej Pelc, David Peleg: The Complexity of Data Mining on the Web (Abstract). 153
• 
  Esteban Feuerstein, Stefano Leonardi, Alberto Marchetti-Spaccamela, Nicola Santoro: Efficient Token-Based Control in Rings (Abstract). 154
• 
  Sonne Preminger, Eli Upfal: Efficient Traffic Laws for Mobile Robots - Work in Progress (Avstract). 155

Session 6

• 
  Yuh-Jzer Joung: Strong-Feasibilities of Equivalence-Completions. 156-165
• 
  Tushar Deepak Chandra: Polylog Randomized Wait-Free Consensus. 166-175
• 
  Phillip B. Gibbons, Yossi Matias, Vijaya Ramachandran: Asynchrony versus Bulk-Synchrony in QRQW PRAM model (Abstract). 176
• 
  Frank A. Stomp, Gadi Taubenfeld: Constructing a Reliable Test&Set Bit (Abstract). 177
• 
  Sibsankar Haldar, K. Vidyasankar: Space-Efficient Construction of Buffer-Optimal 1-Writer 1-Reader Multivalued Atomic Variable (Abstract). 178
• 
  Christos Bouras, Vaggelis Kapoulas, Grammati E. Pantziou, Paul G. Spirakis: Randomized Adaptive Video on Demand (Abstract). 179
• 
  Esther Jennings, Lenka Motyckova: Distributed Algorithms for Sparse k-Connectivity Certificates (Abstract). 180

Session 7

• 
  Eyal Kushilevitz, Yishay Mansour: Randomness in Private Computations. 181-190
• 
  Mihir Bellare, Juan A. Garay, Tal Rabin: Distributed Pseudo-Random Bit Generators - A New Way to Speed-Up Shared Coin Tossing. 191-200
• 
  Arkady Zamsky: A Randomized Byzantine Agreement Protocol with Constant Expected Time and Guaranteed Termination in Optimal (Deterministic) Time. 201-208
• 
  Marcel-Catalin Rosu: Early-Stopping Terminating Reliable Broadcast Protocol for General Omission Failures (Abstract). 209
• 
  Shlomi Dolev, Evangelos Kranakis, Danny Krizanc: Baked Potatoes: Deadlock Prevention Via Scheduling (Abstract). 210
• 
  Yair Frankel, Peter Gemmell, Moti Yung: Witness-Based Cryptographic Program Checking and Applications (an Announcement). 211
• 
  Yehuda Afek, Yishay Mansour, Zvi Ostfeld: On the Convergence Complexity of Optimistic Rate Based Flow Control Algorithms (Brief Announcement). 212

Session 8

• 
  Yehuda Afek, Michael Merritt, Gadi Taubenfeld: The Power of Multi-objects (Extended Abstract). 213-222
• 
  Hagit Attiya, Eyal Dagan: Universal Operations: Unary versus Binary (Extended Abstract). 223-232
• 
  Srikanth Ramamurthy, Mark Moir, James H. Anderson: Real-Time Object Sharing with Minimal System Support (Extended Abstract). 233-242
• 
  John D. Valois: Space Bounds for Transactional Synchronization (Abstract). 243
• 
  Martha J. Kosa: What Critical Algebraic Property Allows Operations of Concurrent Abstract Data Types to be Fast? (Brief Announement). 244
• 
  Soma Chaudhuri, Sundar Kanthadai, Jennifer L. Welch: The Role of Data-Race-Free Programs in Recoverable DSM (Abstract). 245
• 
  Anindya Basu, Bernadette Charron-Bost, Sam Toueg: Crash Failures vs. Crash + Link Failures (Abstract). 246

Session 9

• 
  Mahesh Jayaram, George Varghese: Crash Failures can Drive Protocols to Arbitrary States. 247-256
• 
  Prasad Jayanti, King Tan, Sam Toueg: Time and Space Lower Bounds for Non-Blocking Implementations (Preliminary Version). 257-266
• 
  Maged M. Michael, Michael L. Scott: Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms. 267-275
• 
  Eli Gafni: A Proof of a Theorem in Algebraic Topology by a Distributed Algorithm (Abstract). 276
• 
  Marios Mavronicolas: Wait-Free Solvability Via Combinatorial Topology (Abstract). 277
• 
  Eli Gafni: Simulation as an Iterated Task (Abstract). 278
• 
  Maurice Herlihy, Sergio Rajsbaum: On the Decidability of Distributed Decision Tasks (Brief Announcement). 279

Session 10

• 
  Nancy A. Lynch, Nir Shavit, Alexander A. Shvartsman, Dan Touitou: Counting Networks are Practically Linearizable. 280-289
• 
  David Peleg, Avishai Wool: How to be an Efficient Snoop, or the Probe Complexity of Quorum Systems (Extended Abstract). 290-299
• 
  Alan Fekete, David Gupta, Victor Luchangco, Nancy A. Lynch, Alexander A. Shvartsman: Eventually-Serializable Data Services. 300-309
• 
  Michel Raynal, Gérard Thia-Kime, Mustaque Ahamad: From Serializable to Causal Transactions (Abstract). 310
• 
  Costas Busch, Marios Mavronicolas: The Strength of Counting Networks (Abstract). 311
• 
  Peter Auer, Pasquale Caianiello, Nicolò Cesa-Bianchi: Tight Bounds on the Cumulative Profit of Distributed Voters (Abstract). 312
• 
  Lenore Cowen, Rudolf Mathar: The Offset Problem (Abstract). 313

Session 11

• 
  Christof Fetzer, Flaviu Cristian: Fail-Awareness in Timed Asynchronous Systems. 314-321
• 
  Tushar Deepak Chandra, Vassos Hadzilacos, Sam Toueg, Bernadette Charron-Bost: On the Impossibility of Group Membership. 322-330
• 
  Gil Neiger: A New Look at Membership Services (Extended Abstract). 331-340
• 
  Cynthia Dwork, Ching-Tien Ho, H. Raymond Strong: Collective Consistency (Work in Progress, Abstract). 341
• 
  Aleta Ricciardi: Impossibility of (Repeated) Reliable Broadcast (Abstract). 342
• 
  Danny Dolev, Dalia Malki, H. Raymond Strong: A Framework for Partitionable Membership Service (Abstract). 343
• 
  Yair Amir, Avishai Wool: Evaluating Quorum Systems Over the Internet (Abstract). 344