| 1996 | A Framework for Partitionable Membership Service (Abstract). Danny Dolev, Dalia Malki, H. Raymond Strong |
| 1996 | A New Look at Membership Services (Extended Abstract). Gil Neiger |
| 1996 | A Proof of a Theorem in Algebraic Topology by a Distributed Algorithm (Abstract). Eli Gafni |
| 1996 | A Randomized Byzantine Agreement Protocol with Constant Expected Time and Guaranteed Termination in Optimal (Deterministic) Time. Arkady Zamsky |
| 1996 | About State Recording in Asynchronous Computations (Abstract). Roberto Baldoni, Jean-Michel Hélary, Michel Raynal |
| 1996 | An Efficient Recovery-Based Spin Lock Protocol for Preemptive Shared Memory Multiprocessors. Injong Rhee, Chi-Yung Lee |
| 1996 | An Optimal Algorithm for Generalized Causal Message Ordering (Abstract). Ajay D. Kshemkalyani, Mukesh Singhal |
| 1996 | Asynchrony versus Bulk-Synchrony in QRQW PRAM model (Abstract). Phillip B. Gibbons, Yossi Matias, Vijaya Ramachandran |
| 1996 | Atomicity in Electronic Commerce. J. D. Tygar |
| 1996 | Automated Logical Verification Based on Trace Abstractions. Nils Klarlund, Mogens Nielsen, Kim Sunesen |
| 1996 | Baked Potatoes: Deadlock Prevention Via Scheduling (Abstract). Shlomi Dolev, Evangelos Kranakis, Danny Krizanc |
| 1996 | Characterization of Message Ordering Specifications and Protocols (Abstract). Venkatesh V. Murty, Vijay K. Garg |
| 1996 | Collective Consistency (Work in Progress, Abstract). Cynthia Dwork, Ching-Tien Ho, H. Raymond Strong |
| 1996 | Comparing Primary-Backup and State Machines for Crash Failures (Abstract). Jeremy B. Sussman, Keith Marzullo |
| 1996 | Constructing a Reliable Test&Set Bit (Abstract). Frank A. Stomp, Gadi Taubenfeld |
| 1996 | Counting Networks are Practically Linearizable. Nancy A. Lynch, Nir Shavit, Alexander A. Shvartsman, Dan Touitou |
| 1996 | Crash Failures can Drive Protocols to Arbitrary States. Mahesh Jayaram, George Varghese |
| 1996 | Crash Failures vs. Crash + Link Failures (Abstract). Anindya Basu, Bernadette Charron-Bost, Sam Toueg |
| 1996 | Distributed Algorithms for Sparse k-Connectivity Certificates (Abstract). Esther Jennings, Lenka Motyckova |
| 1996 | Distributed Pseudo-Random Bit Generators - A New Way to Speed-Up Shared Coin Tossing. Mihir Bellare, Juan A. Garay, Tal Rabin |
| 1996 | Early-Stopping Terminating Reliable Broadcast Protocol for General Omission Failures (Abstract). Marcel-Catalin Rosu |
| 1996 | Efficient Delta-Causal Broadcasting of Multimedia Applications (Abstract). Roberto Baldoni, Ravi Prakash, Michel Raynal, Mukesh Singhal |
| 1996 | Efficient Message Ordering in Dynamic Networks. Idit Keidar, Danny Dolev |
| 1996 | Efficient Token-Based Control in Rings (Abstract). Esteban Feuerstein, Stefano Leonardi, Alberto Marchetti-Spaccamela, Nicola Santoro |
| 1996 | Efficient Traffic Laws for Mobile Robots - Work in Progress (Avstract). Sonne Preminger, Eli Upfal |
| 1996 | Evaluating Quorum Systems Over the Internet (Abstract). Yair Amir, Avishai Wool |
| 1996 | Eventually-Serializable Data Services. Alan D. Fekete, David Gupta, Victor Luchangco, Nancy A. Lynch, Alexander A. Shvartsman |
| 1996 | Fail-Awareness in Timed Asynchronous Systems. Christof Fetzer, Flaviu Cristian |
| 1996 | Fast, Long-Lived Renaming Improved and Simplified (Abstract). Mark Moir, Juan A. Garay |
| 1996 | Fault-Containing Self-Stabilizing Algorithms. Sukumar Ghosh, Arobinda Gupta, Ted Herman, Sriram V. Pemmaraju |
| 1996 | From Serializable to Causal Transactions (Abstract). Michel Raynal, Gérard Thia-Kime, Mustaque Ahamad |
| 1996 | Fundamental Challenges in Mobile Computing. Mahadev Satyanarayanan |
| 1996 | How to be an Efficient Snoop, or the Probe Complexity of Quorum Systems (Extended Abstract). David Peleg, Avishai Wool |
| 1996 | I/O Automata Based Verification of Finite State Distributed Systems: Complexity Issues (Abstract). Sandeep K. Shukla, Harry B. Hunt III, Daniel J. Rosenkrantz, S. S. Ravi, Richard Edwin Stearns |
| 1996 | Impossibility of (Repeated) Reliable Broadcast (Abstract). Aleta Ricciardi |
| 1996 | Memory Requirements for Routing in Distributed Networks (Extended Abstract). Cyril Gavoille, Stephane Perennes |
| 1996 | Memory Requirements for Silent Stabilization (Extended Abstract). Shlomi Dolev, Mohamed G. Gouda, Marco Schneider |
| 1996 | Minimizing Access Costs in Replicated Distributed Syste (Abstract). Michael Goldweber, Donald B. Johnson |
| 1996 | On the Borowsky-Gafni Simulation Algorithm (Abstract). Nancy A. Lynch, Sergio Rajsbaum |
| 1996 | On the Convergence Complexity of Optimistic Rate Based Flow Control Algorithms (Brief Announcement). Yehuda Afek, Yishay Mansour, Zvi Ostfeld |
| 1996 | On the Decidability of Distributed Decision Tasks (Brief Announcement). Maurice Herlihy, Sergio Rajsbaum |
| 1996 | On the Impossibility of Group Membership. Tushar Deepak Chandra, Vassos Hadzilacos, Sam Toueg, Bernadette Charron-Bost |
| 1996 | Optimal Routing Tables. Harry Buhrman, Jaap-Henk Hoepman, Paul M. B. Vitányi |
| 1996 | Polylog Randomized Wait-Free Consensus. Tushar Deepak Chandra |
| 1996 | Proceedings of the Fifteenth Annual ACM Symposium on Principles of Distributed Computing, Philadelphia, Pennsylvania, USA, May 23-26, 1996 James E. Burns, Yoram Moses |
| 1996 | Randomized Adaptive Video on Demand (Abstract). Christos Bouras, Vaggelis Kapoulas, Grammati E. Pantziou, Paul G. Spirakis |
| 1996 | Randomness in Private Computations. Eyal Kushilevitz, Yishay Mansour |
| 1996 | Real-Time Object Sharing with Minimal System Support (Extended Abstract). Srikanth Ramamurthy, Mark Moir, James H. Anderson |
| 1996 | Refining Knowledge Oriented Actions to Layered Implementations. Wil Janssen |
| 1996 | Self-Stabilization by Window Washing. Adam M. Costello, George Varghese |
| 1996 | Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms. Maged M. Michael, Michael L. Scott |
| 1996 | Simulation as an Iterated Task (Abstract). Eli Gafni |
| 1996 | Space Bounds for Transactional Synchronization (Abstract). John D. Valois |
| 1996 | Space-Efficient Construction of Buffer-Optimal 1-Writer 1-Reader Multivalued Atomic Variable (Abstract). Sibsankar Haldar, K. Vidyasankar |
| 1996 | Spreading Rumors Rapidly Despite and Adversary. James Aspnes, William Hurwood |
| 1996 | Strong-Feasibilities of Equivalence-Completions. Yuh-Jzer Joung |
| 1996 | Synthesis of Concurrent Systems for an Atomic Read / Atomic Write Model of Computation (Extended Abstract). Paul C. Attie, E. Allen Emerson |
| 1996 | Synthesis of Distributed Control Systems (Abstract). Evelyn Tumlin Pierce |
| 1996 | Testing Concurrent Data Structures (Abstract). John L. Bruno, Phillip B. Gibbons, Steven Phillips |
| 1996 | The Complexity of Data Mining on the Web (Abstract). Evangelos Kranakis, Danny Krizanc, Andrzej Pelc, David Peleg |
| 1996 | The Offset Problem (Abstract). Lenore Cowen, Rudolf Mathar |
| 1996 | The Power of Multi-objects (Extended Abstract). Yehuda Afek, Michael Merritt, Gadi Taubenfeld |
| 1996 | The Role of Data-Race-Free Programs in Recoverable DSM (Abstract). Soma Chaudhuri, Sundar Kanthadai, Jennifer L. Welch |
| 1996 | The Strength of Counting Networks (Abstract). Costas Busch, Marios Mavronicolas |
| 1996 | Tight Bounds on the Cumulative Profit of Distributed Voters (Abstract). Peter Auer, Pasquale Caianiello, Nicolò Cesa-Bianchi |
| 1996 | Time and Space Lower Bounds for Non-Blocking Implementations (Preliminary Version). Prasad Jayanti, King Tan, Sam Toueg |
| 1996 | Trade-Offs in Implementing Optimal Message Logging Protocols. Lorenzo Alvisi, Keith Marzullo |
| 1996 | Universal Operations: Unary versus Binary (Extended Abstract). Hagit Attiya, Eyal Dagan |
| 1996 | Using Events Structures for the Efficient Analysis of State Graphs (Abstract). Dominique Ambroise, Brigitte Rozoy |
| 1996 | Wait-Free Solvability Via Combinatorial Topology (Abstract). Marios Mavronicolas |
| 1996 | What Critical Algebraic Property Allows Operations of Concurrent Abstract Data Types to be Fast? (Brief Announement). Martha J. Kosa |
| 1996 | Witness-Based Cryptographic Program Checking and Applications (an Announcement). Yair Frankel, Peter Gemmell, Moti Yung |