Distributed System Design

Introduction.- Distributed Programming Languages.- Formal Approaches to Distributed Systems Design.- Mutual Exclusion and Election Algorithms.- Prevention and Detection of Deadlock.- Reliability in Distributed Systems.- Distributed Routing Algorithms.- Distributed Data Management.- Distributed Systems Applications.- Appendix.

Future requirements for computing speed, system reliability, and cost-effectiveness entail the development of alternative computers to replace the traditional von Neumann organization. As computing networks come into being, one of the latest dreams is now possible - distributed computing. Distributed computing brings transparent access to as much computer power and data as the user needs for accomplishing any given task - simultaneously achieving high performance and reliability.The subject of distributed computing is diverse, and many researchers are investigating various issues concerning the structure of hardware and the design of distributed software. Distributed System Design defines a distributed system as one that looks to its users like an ordinary system, but runs on a set of autonomous processing elements (PEs) where each PE has a separate physical memory space and the message transmission delay is not negligible. With close cooperation among these PEs, the system supports an arbitrary number of processes and dynamic extensions.Distributed System Design outlines the main motivations for building a distributed system, including:inherently distributed applicationsperformance/costresource sharingflexibility and extendibilityavailability and fault tolerancescalabilityPresenting basic concepts, problems, and possible solutions, this reference serves graduate students in distributed system design as well as computer professionals analyzing and designing distributed/open/parallel systems.Chapters discuss:the scope of distributed computing systemsgeneral distributed programming languages and a CSP-like distributed control description language (DCDL)expressing parallelism, interprocess communication and synchronization, and fault-tolerant designtwo approaches describing a distributed system: the time-space view and the interleaving viewmutual exclusion and related issues, including election, bidding, and self-stabilizationprevention and detection of deadlockreliability, safety, and security as well as various methods of handling node, communication, Byzantine, and software faultsefficient interprocessor communication mechanisms as well as these mechanisms without specific constraints, such as adaptiveness, deadlock-freedom, and fault-tolerancevirtual channels and virtual networksload distribution problemssynchronization of access to shared data while supporting a high degree of concurrency

IntroductionMotivationBasic Computer OrganizationsDefinition of a Distributed SystemOur ModelInterconnection NetworksApplications and StandardsScopeSource of ReferencesDistributed Programming LanguagesRequirement for Distributed Programming SupportAn Overview of Parallel/Distributed Programming LanguageExpressing ParallelismProcess Communication and SynchronizationRemote Procedure CallsRobustnessFormal Approaches to Distributed Systems DesignIntroduction to ModelsCausally Related EventsGlobal StatesLogical ClocksApplicationsClassification of Distributed Control AlgorithmsThe Complexity of Distributed AlgorithmsMutual Exclusion and Election AlgorithmsMutual ExclusionNon-Token-Based SolutionsToken-Based SolutionsElectionBiddingSelf-StabilizationPrevention, Avoidance, and Detection of DeadlockThe Deadlock ProblemDeadlock PreventionA Deadlock Prevention Example: Distributed Database SystemsDeadlock AvoidanceA Deadlock Prevention Example: Multi-Robot Flexible Assembly CellsDeadlock Detection and RecoveryDeadlock Detection and Recovery ExamplesDistributed Routing AlgorithmsIntroductionGeneral-Purpose Shortest Path RoutingUnicasting in Special-Purpose NetworksBroadcasting in Special-Purpose NetworksMulticasting in Special-Purpose NetworksAdaptive Deadlock-Free, and Fault-Tolerant RoutingVirtual Channels and Virtual NetworksFully Adaptive and Deadlock-Free RoutingPartially Adaptive and Deadlock-Free RoutingFault-Tolerant Unicasting: General ApproachesFault-Tolerant Unicasting in 2-D Meshes and ToriFault-Tolerant Unicasting in HypercubesFault-Tolerant BroadcastingFault-Tolerant MulticastingReliability in Distributed SystemsBasic ModelsBuilding Blocks of Fault-Tolerant DesignHandling of Node FaultsIssues in Backward RecoveryHandling of Byzantine FaultsHandling of Communication FaultsHandling of Storage FaultsStatic Load DistributionClassification of Load DistributionStatic Load DistributionAn Overview of Different Scheduling ModelsTask Scheduling Based on Task Precedent GraphsCase Study: Two Optimal Scheduling AlgorithmsTask Scheduling Based on Task Interaction GraphsCase Study: Domain PartitionScheduling Using Other Models and ObjectivesFuture DirectionsDynamic Load DistributionDynamic Load DistributionLoad Balancing Design DecisionsMigration Policies: Sender-Initiated and Receiver-InitiatedParameters Used for Load BalancingOther Relevant IssuesSample Load Balancing AlgorithmsCase Study: Load Balancing on Hypercube MulticomputersFuture DirectionsDistributed Data ManagementBasic ConceptsSerializability TheoryConcurrency ControlReplica and Consistency ManagementDistributed Reliability ProtocolsDistributed System ApplicationsDistributed Operating SystemsDistributed File SystemsDistributed Shared MemoryDistributed Database SystemsHeterogeneous ProcessingFuture Directions of Distributed Systems

Jie Wu