Concurrent and Distributed Computing in Java

Concurrent and Distributed Computing in Java

by Vijay K. Garg
Released February 2004
Publisher(s): Wiley-IEEE Press
ISBN: 9780471432302

Read it now on the O’Reilly learning platform with a 10-day free trial.

O’Reilly members get unlimited access to books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.

Start your free trial

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.

Table of contents

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

Product information

  • Title: Concurrent and Distributed Computing in Java
  • Author(s): Vijay K. Garg
  • Release date: February 2004
  • Publisher(s): Wiley-IEEE Press
  • ISBN: 9780471432302