DISTRIBUTED COMPUTING

By Y. JONAY

CONTENTS INTRODUCTION DEFINITION RELATION TO COMPUTER SYSTEM COMPONENTS MOTIVATION RELATION TO PARALLEL MULTIPROCESSOR/MULTICOMPUTER SYSTEMS MESSAGE-PASSING SYSTEMS VERSUS SHARED MEMORY SYSTEMS PRIMITIVES FOR DISTRIBUTED COMMUNICATION SYNCHRONOUS VERSUS ASYNCHRONOUS EXECUTIONS DESIGN ISSUES AND CHALLENGES SELECTION AND COVERAGE OF TOPICS CHAPTER SUMMARY EXERCISES NOTES ON REFERENCES REFERENCES A MODEL OF DISTRIBUTED COMPUTATIONS A DISTRIBUTED PROGRAM A MODEL OF DISTRIBUTED EXECUTIONS MODELS OF COMMUNICATION NETWORKS GLOBAL STATE OF A DISTRIBUTED SYSTEM CUTS OF A DISTRIBUTED COMPUTATION PAST AND FUTURE CONES OF AN EVENT MODELS OF PROCESS COMMUNICATIONS LOGICAL TIME A FRAMEWORK FOR A SYSTEM OF LOGICAL CLOCKS SCALAR TIME VECTOR TIME EFFICIENT IMPLEMENTATIONS OF VECTOR CLOCKS JARD–JOURDAN’S ADAPTIVE TECHNIQUE MATRIX TIME VIRTUAL TIME PHYSICAL CLOCK SYNCHRONIZATION: NTP GLOBAL STATE AND SNAPSHOT RECORDING ALGORITHMS SYSTEM MODEL AND DEFINITIONS SNAPSHOT ALGORITHMS FOR FIFO CHANNELS VARIATIONS OF THE CHANDY–LAMPORT ALGORITHM SNAPSHOT ALGORITHMS FOR NON-FIFO CHANNELS SNAPSHOTS IN A CAUSAL DELIVERY SYSTEM MONITORING GLOBAL STATE NECESSARY AND SUFFICIENT CONDITIONS FOR CONSISTENT GLOBAL SNAPSHOTS FINDING CONSISTENT GLOBAL SNAPSHOTS IN A DISTRIBUTED COMPUTATION TERMINOLOGY AND BASIC ALGORITHMS TOPOLOGY ABSTRACTION AND OVERLAYS CLASSIFICATIONS AND BASIC CONCEPTS COMPLEXITY MEASURES AND METRICS PROGRAM STRUCTURE ELEMENTARY GRAPH ALGORITHMS SYNCHRONIZERS MAXIMAL INDEPENDENT SET (MIS) CONNECTED DOMINATING SET COMPACT ROUTING TABLES LEADER ELECTION CHALLENGES IN DESIGNING DISTRIBUTED GRAPH ALGORITHMS OBJECT REPLICATION PROBLEMS MESSAGE ORDERING AND GROUP COMMUNICATION MESSAGE ORDERING PARADIGMS ASYNCHRONOUS EXECUTION WITH SYNCHRONOUS COMMUNICATION SYNCHRONOUS PROGRAM ORDER ON AN ASYNCHRONOUS SYSTEM GROUP COMMUNICATION CAUSAL ORDER (CO) TOTAL ORDER A NOMENCLATURE FOR MULTICAST PROPAGATION TREES FOR MULTICAST CLASSIFICATION OF APPLICATION-LEVEL MULTICAST ALGORITHMS SEMANTICS OF FAULT-TOLERANT GROUP COMMUNICATION DISTRIBUTED MULTICAST ALGORITHMS AT THE NETWORK LAYER TERMINATION DETECTION SYSTEM MODEL OF A DISTRIBUTED COMPUTATION TERMINATION DETECTION USING DISTRIBUTED SNAPSHOTS TERMINATION DETECTION BY WEIGHT THROWING A SPANNING-TREE-BASED TERMINATION DETECTION ALGORITHM MESSAGE-OPTIMAL TERMINATION DETECTION TERMINATION DETECTION IN A VERY GENERAL DISTRIBUTED COMPUTING MODEL TERMINATION DETECTION IN THE ATOMIC COMPUTATION MODEL TERMINATION DETECTION IN A FAULTY DISTRIBUTED SYSTEM REASONING WITH KNOWLEDGE THE MUDDY CHILDREN PUZZLE LOGIC OF KNOWLEDGE KNOWLEDGE IN SYNCHRONOUS SYSTEMS KNOWLEDGE IN ASYNCHRONOUS SYSTEMS KNOWLEDGE TRANSFER KNOWLEDGE AND CLOCKS DISTRIBUTED MUTUAL EXCLUSION ALGORITHMS PRELIMINARIES LAMPORT’S ALGORITHM RICART–AGRAWALA ALGORITHM SINGHAL’S DYNAMIC INFORMATION-STRUCTURE ALGORITHM LODHA AND KSHEMKALYANI’S FAIR MUTUAL EXCLUSION ALGORITHM QUORUM-BASED MUTUAL EXCLUSION ALGORITHMS MAEKAWA’S ALGORITHM AGARWAL–EL ABBADI QUORUM-BASED ALGORITHM TOKEN-BASED ALGORITHMS SUZUKI–KASAMI’S BROADCAST ALGORITHM RAYMOND’S TREE-BASED ALGORITHM DEADLOCK DETECTION IN DISTRIBUTED SYSTEMS SYSTEM MODEL MODELS OF DEADLOCKS KNAPP’S CLASSIFICATION OF DISTRIBUTED DEADLOCK DETECTION ALGORITHMS MITCHELL AND MERRITT’S ALGORITHM FOR THE SINGLE- RESOURCE MODEL CHANDY–MISRA–HAAS ALGORITHM FOR THE AND MODEL CHANDY–MISRA–HAAS ALGORITHM FOR THE OR MODEL KSHEMKALYANI–SINGHAL ALGORITHM FOR THE P-OUT-OF-Q MODEL GLOBAL PREDICATE DETECTION STABLE AND UNSTABLE PREDICATES MODALITIES ON PREDICATES CENTRALIZED ALGORITHM FOR RELATIONAL PREDICATES CONJUNCTIVE PREDICATES DISTRIBUTED ALGORITHMS FOR CONJUNCTIVE PREDICATES FURTHER CLASSIFICATION OF PREDICATES DISTRIBUTED SHARED MEMORY ABSTRACTION AND ADVANTAGES MEMORY CONSISTENCY MODELS SHARED MEMORY MUTUAL EXCLUSION WAIT-FREEDOM REGISTER HIERARCHY AND WAIT-FREE SIMULATIONS WAIT-FREE ATOMIC SNAPSHOTS OF SHARED OBJECTS CHECKPOINTING AND ROLLBACK RECOVERY BACKGROUND AND DEFINITIONS ISSUES IN FAILURE RECOVERY CHECKPOINT-BASED RECOVERY LOG-BASED ROLLBACK RECOVERY KOO–TOUEG COORDINATED CHECKPOINTING ALGORITHM JUANG–VENKATESAN ALGORITHM FOR ASYNCHRONOUS CHECKPOINTING AND RECOVERY MANIVANNAN–SINGHAL QUASI-SYNCHRONOUS CHECKPOINTING ALGORITHM PETERSON–KEARNS ALGORITHM BASED ON VECTOR TIME HELARY–MOSTEFAOUI–NETZER–RAYNAL COMMUNICATION-INDUCED PROTOCOL CONSENSUS AND AGREEMENT ALGORITHMS PROBLEM DEFINITION OVERVIEW OF RESULTS AGREEMENT IN A FAILURE-FREE SYSTEM (SYNCHRONOUS OR ASYNCHRONOUS) AGREEMENT IN (MESSAGE-PASSING) SYNCHRONOUS SYSTEMS WITH FAILURES AGREEMENT IN ASYNCHRONOUS MESSAGE-PASSING SYSTEMS WITH FAILURES WAIT-FREE SHARED MEMORY CONSENSUS IN ASYNCHRONOUS SYSTEMS FAILURE DETECTORS UNRELIABLE FAILURE DETECTORS THE CONSENSUS PROBLEM ATOMIC BROADCAST A SOLUTION TO ATOMIC BROADCAST THE WEAKEST FAILURE DETECTORS TO SOLVE FUNDAMENTAL AGREEMENT PROBLEMS AN IMPLEMENTATION OF A FAILURE DETECTOR AN ADAPTIVE FAILURE DETECTION PROTOCOL AUTHENTICATION IN DISTRIBUTED SYSTEMS PROTOCOLS BASED ON SYMMETRIC CRYPTOSYSTEMS PROTOCOLS BASED ON ASYMMETRIC CRYPTOSYSTEMS PASSWORD-BASED AUTHENTICATION AUTHENTICATION PROTOCOL FAILURES SELF-STABILIZATION DEFINITION OF SELF-STABILIZATION ISSUES IN THE DESIGN OF SELF-STABILIZATION ALGORITHMS METHODOLOGIES FOR DESIGNING SELF-STABILIZING SYSTEMS COMMUNICATION PROTOCOLS SELF-STABILIZING DISTRIBUTED SPANNING TREES SELF-STABILIZING ALGORITHMS FOR SPANNING-TREE CONSTRUCTION AN ANONYMOUS SELF-STABILIZING ALGORITHM FOR 1-MAXIMAL INDEPENDENT SET IN TREES A PROBABILISTIC SELF-STABILIZING LEADER ELECTION ALGORITHM THE ROLE OF COMPILERS IN SELF-STABILIZATION SELF-STABILIZATION AS A SOLUTION TO FAULT TOLERANCE FACTORS PREVENTING SELF-STABILIZATION LIMITATIONS OF SELF-STABILIZATION PEER-TO-PEER COMPUTING AND OVERLAY GRAPHS UNSTRUCTURED OVERLAYS CHORD DISTRIBUTED HASH TABLE CONTENT ADDRESSIBLE NETWORKS (CAN) TAPESTRY SOME OTHER CHALLENGES IN P2P SYSTEM DESIGN TRADEOFFS BETWEEN TABLE STORAGE AND ROUTE LENGTHS GRAPH STRUCTURES OF COMPLEX NETWORKS INTERNET GRAPHS GENERALIZED RANDOM GRAPH NETWORKS SMALL-WORLD NETWORKS SCALE-FREE NETWORKS EVOLVING NETWORKS