15. PODC 1996: Philadelphia, Pennsylvania, USA

Proceedings of the Fifteenth Annual ACM Symposium on Principles of Distributed Computing, Philadelphia, Pennsylvania, USA, May 23-26, 1996. ACM, ISBN 0-89791-800-2

Invited Speakers

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

Session 1

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

Session 2

Joint ISCA/PODC Panel and Discussion

Session 3

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

Session 4

Wil Janssen: Refining Knowledge Oriented Actions to Layered Implementations. 91-100 BibTeX
Nils Klarlund, Mogens Nielsen, Kim Sunesen: Automated Logical Verification Based on Trace Abstractions. 101-110 BibTeX
Paul C. Attie, E. Allen Emerson: Synthesis of Concurrent Systems for an Atomic Read / Atomic Write Model of Computation (Extended Abstract). 111-120 BibTeX
Evelyn Tumlin Pierce: Synthesis of Distributed Control Systems (Abstract). 121 BibTeX
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 BibTeX
Dominique Ambroise, Brigitte Rozoy: Using Events Structures for the Efficient Analysis of State Graphs (Abstract). 123 BibTeX
John L. Bruno, Phillip B. Gibbons, Steven Phillips: Testing Concurrent Data Structures (Abstract). 124 BibTeX

Session 5

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

Session 6

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

Session 7

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

Session 8

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

Session 9

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

Session 10

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

Session 11

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