| 1996 | Time and Space Lower Bounds for Non-Blocking Implementations (Preliminary Version). | Prasad Jayanti, King Tan, Sam Toueg |
| 1996 | Refining Knowledge Oriented Actions to Layered Implementations. | Wil Janssen |
| 1996 | On the Decidability of Distributed Decision Tasks (Brief Announcement). | Maurice Herlihy, Sergio Rajsbaum |
| 1996 | Space-Efficient Construction of Buffer-Optimal 1-Writer 1-Reader Multivalued Atomic Variable (Abstract). | Sibsankar Haldar, K. Vidyasankar |
| 1996 | Minimizing Access Costs in Replicated Distributed Syste (Abstract). | Michael Goldweber, Donald B. Johnson |
| 1996 | Asynchrony versus Bulk-Synchrony in QRQW PRAM model (Abstract). | Phillip B. Gibbons, Yossi Matias, Vijaya Ramachandran |
| 1996 | Fault-Containing Self-Stabilizing Algorithms. | Sukumar Ghosh, Arobinda Gupta, Ted Herman, Sriram V. Pemmaraju |
| 1996 | Memory Requirements for Routing in Distributed Networks (Extended Abstract). | Cyril Gavoille, Stephane Perennes |
| 1996 | Simulation as an Iterated Task (Abstract). | Eli Gafni |
| 1996 | A Proof of a Theorem in Algebraic Topology by a Distributed Algorithm (Abstract). | Eli Gafni |
| 1996 | Witness-Based Cryptographic Program Checking and Applications (an Announcement). | Yair Frankel, Peter Gemmell, Moti Yung |
| 1996 | Efficient Token-Based Control in Rings (Abstract). | Esteban Feuerstein, Stefano Leonardi, Alberto Marchetti-Spaccamela, Nicola Santoro |
| 1996 | Fail-Awareness in Timed Asynchronous Systems. | Christof Fetzer, Flaviu Cristian |
| 1996 | Eventually-Serializable Data Services. | Alan D. Fekete, David Gupta, Victor Luchangco, Nancy A. Lynch, Alexander A. Shvartsman |
| 1996 | Collective Consistency (Work in Progress, Abstract). | Cynthia Dwork, Ching-Tien Ho, H. Raymond Strong |
| 1996 | A Framework for Partitionable Membership Service (Abstract). | Danny Dolev, Dalia Malki, H. Raymond Strong |
| 1996 | Baked Potatoes: Deadlock Prevention Via Scheduling (Abstract). | Shlomi Dolev, Evangelos Kranakis, Danny Krizanc |
| 1996 | Memory Requirements for Silent Stabilization (Extended Abstract). | Shlomi Dolev, Mohamed G. Gouda, Marco Schneider |
| 1996 | The Offset Problem (Abstract). | Lenore Cowen, Rudolf Mathar |
| 1996 | Self-Stabilization by Window Washing. | Adam M. Costello, George Varghese |
| 1996 | The Role of Data-Race-Free Programs in Recoverable DSM (Abstract). | Soma Chaudhuri, Sundar Kanthadai, Jennifer L. Welch |
| 1996 | On the Impossibility of Group Membership. | Tushar Deepak Chandra, Vassos Hadzilacos, Sam Toueg, Bernadette Charron-Bost |
| 1996 | Polylog Randomized Wait-Free Consensus. | Tushar Deepak Chandra |
| 1996 | The Strength of Counting Networks (Abstract). | Costas Busch, Marios Mavronicolas |
| 1996 | Optimal Routing Tables. | Harry Buhrman, Jaap-Henk Hoepman, Paul M. B. Vitnyi |