14. PODC 1995: Ottawa, Ontario, Canada

Proceedings of the Fourteenth Annual ACM Symposium on Principles of Distributed Computing, Ottawa, Ontario, Canada, August 20-23, 1995. ACM, ISBN 0-89791-710-3

Invited Lectures at 1994 PODC

Jonathan S. Turner: Issues in Distributed Control for ATM Networks. 2-16
David A. Patterson, David E. Culler, Thomas E. Anderson: A Case for NOW (Networks of Workstations) - Abstract. 17

Log Presentations

Session L1

Shay Kutten, David Peleg: Fault-Local Distributed Mending (Extended Abstract). 20-27
Ramakrishna Thurimella: Sub-linear Distributed Algorithms for Sparse Certificates and Biconnected Components (Extended Abstract). 28-37
Rafail Ostrovsky, Daniel Shawcross Wilkerson: Faster Computation On Directed Networks of Automata (Extended Abstract). 38-46
Ravi Prakash, Niranjan G. Shivaratri, Mukesh Singhal: Distributed Dynamic Channel Allocation for Mobile Computing. 47-56

Session L2

Umesh Maheshwari, Barbara Liskov: Collecting Cyclic Distributed Garbage Using Heuristics to Control Migration. 57-63
Manhoi Choy, Hong Va Leong, Man Hon Wong: On Distributed Object Checkpointing and Recovery. 64-73
E. N. Elnozahy: On the Relevance of Communication Costs of Rollback-Recovery Protocols. 74-79
Robbert van Renesse, Kenneth P. Birman, Roy Friedman, Mark Hayden, David A. Karr: A Framework for Protocol Composition in Horus. 80-89

Session L3

Maurice Herlihy, Sergio Rajsbaum: Algebraic Spans (Preliminary Version). 90-99
Gil Neiger: Failure Detectors and the Wait-Free Hierarchy. 100-109
Wai-Kau Lo: More on t-Resilience vs. Wait-Freedom (Extended Abstract). 110-119

Session L4

David Peleg, Avishai Wool: Crumbling Walls: A Class of Practical and Efficient Quorum Systems (Extended Abstract). 120-129
Rosario Gennaro: Achieving Independence Efficiently and Securely. 130-136
Christof Fetzer, Flaviu Cristian: Lower Bounds for Convergence Function Based Clock Synchronization. 137-143

Session L5

Nalini Venkatasubramanian, Carolyn L. Talcott: Reasoning about Meta Level Activities in Open Distributed Systems. 144-152
Ronald Fagin, Joseph Y. Halpern, Yoram Moses, Moshe Y. Vardi: Knowledge-Based Programs. 153-163
Crispin Cowan, Hanan Lutfiyya: Formal Semantics for Expressing Optimism: The Meaning of HOPE. 164-173
Anna Pogosyants, Roberto Segala: Formal Verification of Timed Properties for Randomized Distributed Algorithms. 174-183

Session L6

James H. Anderson, Mark Moir: Universal Constructions for Multi-Object Operations. 184-193
Harry Buhrman, Juan A. Garay, Jaap-Henk Hoepman, Mark Moir: Long-Lived Renaming Made Fast. 194-203
Nir Shavit, Dan Touitou: Software Transactional Memory. 204-213
John D. Valois: Lock-Free Linked Lists Using Compare-and-Swap. 214-222

Session L7

Pierre Fraigniaud, Cyril Gavoille: Memory Requirement for Universal Routing Schemes. 223-230
Michalis Faloutsos, Mart Molle: Optimal Distributed Algorithm for Minimum Spanning Trees Revisited. 231-237
Shay Kutten, David Peleg: Fast Distributed Construction of k-Dominating Sets and Applications. 238-249

Brief Announcements

Session B1

James Aspnes, Orli Waarts: A Modular Measure of Competitiveness for Distributed Algorithms (Abstract). 252
Vaggelis Kapoulas, Paul G. Spirakis: Randomized Competitive Algorithms for Admission Control in General Networks (Abstract). 253
Eyal Kushilevitz, Rafail Ostrovsky, Adi Rosén: Log-Space Polynomial End-to-End Communication (Abstract). 254
Shlomi Dolev, Ted Herman: SuperStabilizing Protocols for Dynamic Distributed Systems (Abstract). 255
Shlomi Dolev, Jennifer L. Welch: Self-Stabilizing Clock Synchronization in the Presence of Byzantine Faults (Abstract). 256
Pau-Chen Cheng, Juan A. Garay, Amir Herzberg, Hugo Krawczyk: Securing the Internet (Abstract). 257
M. Abayan, H. Raymond Strong, Edward L. Wimmers: The RAPID C++ Environment (Abstract). 258
Michael Ogg, Aleta Ricciardi: Architecture Decisions for Wide Area Applications (Abstract). 259
Tim Kindberg: A Sequencing Service for Group Communication (Abstract). 260

Session B2

Mehrdad Samadani, Erich Kaltofen: Prediction Based Task Scheduling in Distributed Computing (Abstract). 261
Shikharesh Majumdar, Tom Phillips: Scheduling in Client-Server Systems (Abstract). 262
Lorenzo Alvisi, Keith Marzullo: Deriving Optimal Checkpoint Protocols for Distributed Shared Memory Architectures (Abstract). 263
Parvathi Chundi, Ragini Narasimhan, Daniel J. Rosenkrantz, S. S. Ravi: Active Client Primary-Backup Protocols (Abstract). 264
Evaggelia Pitoura, Aidong Zhang, Bharat K. Bhargava: A View-Based Approach to Relaxing Global Serializability in a Multidatabase System (Abstract). 265
Gurdip Singh: Constraint-based Structuring of Distributed Protocols (Abstract). 266
Hans van der Schoot, Hasan Ural: Generalizing Fair Reachability Analysis to Protocols with Arbitrary Topology (Abstract). 267
Aamod Sane, Roy H. Campbell: Compiling Knowledge-Based Programs (Abstract). 268
Gordon V. Cormack: A Calculus for Concurrent Update (Abstract). 269

Session B3

Martha J. Kosa: Lazy-Writer Multivalued Registers (Abstract). 270
Eli Gafni, Elias Koutsoupias: 3-Processor Tasks Are Undecidable (Abstract). 271
James H. Anderson, Srikanth Ramamurthy: Using Lock-Free Objects in Hard Real-Time Applications (Abstract). 272
Jerry James, Ambuj K. Singh: Complete Implementations for Shared Memory Consistency Conditions (Abstract). 273
Costas Busch, Marios Mavronicolas: A Logarithmic Depth Counting Network (Abstract). 274
Sarantos Kapidakis, Marios Mavronicolas: Load Balancing Networks (Abstract). 275