Book Description Concurrent and Distributed Computing in Java addresses fundamental concepts in concurrent computing with Java examples. The book consists of two parts. The first part deals with techniques for programming in shared-memory based systems. The book covers concepts in Java such as threads, synchronized methods, waits, and notify to expose students to basic concepts for multi-threaded programming. It also includes algorithms for mutual exclusion, consensus, atomic objects, and wait-free data structures. The second part of the book deals with programming in a message-passing system. This part covers resource allocation problems, logical clocks, global property detection, leader election, message ordering, agreement algorithms, checkpointing, and message logging. Primarily a textbook for upper-level undergraduates and graduate students, this thorough treatment will also be of interest to professional programmers. Show and hide more
Table of Contents
Cover Page Title Page Copyright Page List of Figures Preface Chapter 1: Introduction 1.1 Introduction 1.2 Distributed Systems versus Parallel Systems 1.3 Overview of the Book 1.4 Characteristics of Parallel and Distributed Systems 1.5 Design Goals 1.6 Specification of Processes and Tasks 1.6.1 Runnable Interface 1.6.2 Join Construct in Java 1.6.3 Thread Scheduling 1.7 Problems 1.8 Bibliographic Remarks Chapter 2: Mutual Exclusion Problem 2.1 Introduction 2.2 Peterson’s Algorithm 2.3 Lamport’s Bakery Algorithm 2.4 Hardware Solutions 2.4.1 Disabling Interrupts 2.4.2 Instructions with Higher Atomicity 2.5 Problems 2.6 Bibliographic Remarks Chapter 3: Synchronization Primitives 3.1 Introduction 3.2 Semaphores 3.2.1 The Producer-Consumer Problem 3.2.2 The Reader-Writer Problem 3.2.3 The Dining Philosopher Problem 3.3 Monitors 3.4 Other Examples 3.5 Dangers of Deadlocks 3.6 Problems 3.7 Bibliographic Remarks Chapter 4: Consistency Conditions 4.1 Introduction 4.2 System Model 4.3 Sequential Consistency 4.4 Linearizability 4.5 Other Consistency Conditions 4.6 Problems 4.7 Bibliographic Remarks Chapter 5: Wait-Free Synchronization 5.1 Introduction 5.2 Safe, Regular, and Atomic Registers 5.3 Regular SRSW Register 5.4 SRSW Multivalued Register 5.5 MRSW Register 5.6 MRMW Register 5.7 Atomic Snapshots 5.8 Consensus 5.9 Universal Constructions 5.10 Problems 5.11 Bibliographic Remarks Chapter 6: Distributed Programming 6.1 Introduction 6.2 InetAddress Class 6.3 Sockets based on UDP 6.3.1 Datagram Sockets 6.3.2 Datagram Packet Class 6.3.3 Example Using Datagrams 6.4 Sockets Based on TCP 6.4.1 Server Sockets 6.4.2 Example 1: A Name Server 6.4.3 Example 2: A Linker 6.5 Remote Method Invocations 6.5.1 Remote Objects 6.5.2 Parameter Passing 6.5.3 Dealing with Failures 6.5.4 Client Program 6.6 Other Useful Classes 6.7 Problems 6.8 Bibliographic Remarks Chapter 7: Models and Clocks 7.1 Introduction 7.2 Model of a Distributed System 7.3 Model of a Distributed Computation 7.3.1 Interleaving Model 7.3.2 Happened-Before Model 7.4 Logical Clocks 7.5 Vector Clocks 7.6 Direct-Dependency Clocks 7.7 Matrix Clocks 7.8 Problems 7.9 Bibliographic Remarks Chapter 8: Resource Allocation 8.1 Introduction 8.2 Specification of the Mutual Exclusion Problem 8.3 Centralized Algorithm 8.4 Lamport’s Algorithm 8.5 Ricart and Agrawala’s Algorithm 8.6 Dining Philosopher Algorithm 8.7 Token-Based Algorithms 8.8 Quorum-Based Algorithms 8.9 Problems 8.10 Bibliographic Remarks Chapter 9: Global Snapshot 9.1 Introduction 9.2 Chandy and Lamport’s Global Snapshot Algorithm 9.3 Global Snapshots for non-FIFO Channels 9.4 Channel Recording by the Sender 9.5 Application: Checkpointing a Distributed Application 9.6 Problems 9.7 Bibliographic Remarks Chapter 10: Global Properties 10.1 Introduction 10.2 Unstable Predicate Detection 10.3 Application: Distributed Debugging 10.4 A Token-Based Algorithm for Detecting Predicates 10.5 Problems 10.6 Bibliographic Remarks Chapter 11: Detecting Termination and Deadlocks 11.1 Introduction 11.2 Diffusing Computation 11.3 Dijkstra and Scholten’s Algorithm 11.3.1 An Optimization 11.4 Termination Detection without Acknowledgment Messages 11.5 Locally Stable Predicates 11.6 Application: Deadlock Detection 11.7 Problems 11.8 Bibliographic Remarks Chapter 12: Message Ordering 12.1 Introduction 12.2 Causal Ordering 12.2.1 Application: Causal Chat 12.3 Synchronous Ordering 12.4 Total Order for Multicast Messages 12.4.1 Centralized Algorithm 12.4.2 Lamport’s Algorithm for Total Order 12.4.3 Skeen’s Algorithm 12.4.4 Application: Replicated State Machines 12.5 Problems 12.6 Bibliographic Remarks Chapter 13: Leader Election 13.1 Introduction 13.2 Ring-Based Algorithms 13.2.1 Chang-Roberts Algorithm 13.2.2 Hirschberg-Sinclair Algorithm 13.3 Election on General Graphs 13.3.1 Spanning Tree Construction 13.4 Application: Computing Global Functions 13.5 Problems 13.6 Bibliographic Remarks Chapter 14: Synchronizers 14.1 Introduction 14.2 A Simple Synchronizer 14.2.1 Application: BFS Tree Construction 14.3 Synchronizer α 14.4 Synchronizer β 14.5 Synchronizer γ 14.6 Problems 14.7 Bibliographic Remarks Chapter 15: Agreement 15.1 Introduction 15.2 Consensus in Asynchronous Systems (Impossibility) 15.3 Application: Terminating Reliable Broadcast 15.4 Consensus in Synchronous Systems 15.4.1 Consensus under Crash Failures 15.4.2 Consensus under Byzantine Faults 15.5 Knowledge and Common Knowledge 15.6 Application: Two-General Problem 15.7 Problems 15.8 Bibliographic Remarks Chapter 16: Transactions 16.1 Introduction 16.2 ACID Properties 16.3 Concurrency Control 16.4 Dealing with Failures 16.5 Distributed Commit 16.6 Problems 16.7 Bibliographic Remarks Chapter 17: Recovery 17.1 Introduction 17.2 Zigzag Relation 17.3 Communication-Induced Checkpointing 17.4 Optimistic Message Logging: Main Ideas 17.4.1 Model 17.4.2 Fault-Tolerant Vector Clock 17.4.3 Version End Table 17.5 An Asynchronous Recovery Protocol 17.5.1 Message Receive 17.5.2 On Restart after a Failure 17.5.3 On Receiving a Token 17.5.4 On Rollback 17.6 Problems 17.7 Bibliographic Remarks Chapter 18: Self-Stabilization 18.1 Introduction 18.2 Mutual Exclusion with K-State Machines 18.3 Self-Stabilizing Spanning Tree Construction 18.4 Problems 18.5 Bibliographic Remarks A. Various Utility Classes Bibliography Index