Concurrent and Distributed Computing in Java -- Contents -- List of Figures -- Preface -- 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 -- 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 -- 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 -- 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 -- 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 -- 6 Distributed Programming -- 6.1 Introduction -- 6.2 InetAddress Class -- 6.3 Sockets based on UDP -- 6.3.1 Datagram Sockets -- 6.3.2 DatagramPacket 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 -- 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 -- 7.7 Matrix Clocks -- 7.8 Problems -- 7.9 Bibliographic Remarks -- 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 -- 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 -- 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 -- 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 -- 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 -- 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 -- 14 Synchronizers -- 14.1 Introduction -- 14.2 A Simple Synchronizer -- 14.2.1 Application: BFS Tree Construction -- 14.3 Synchronizer a -- 14.4 Synchronizer b -- 14.5 Synchronizer g -- 14.6 Problems -- 14.7 Bibliographic Remarks -- 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 -- 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 -- 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 -- 18 Self-Stabilization -- 18.1 Introduction -- 18.2 Mutual Exclusion with K-State Machines.

18.3 Self-St abilizing Spanning Tree Construction -- 18.4 Problems -- 18.5 Bibliographic Remarks -- A. Various Utility Classes -- Bibliography -- Index -- List of Figures -- 1.1 A parallel system -- 1.2 A distributed system -- 1.3 A process with four threads -- 1.4 HelloWorldThread.java -- 1.5 FooBar.java -- 1.6 Fibonacci.java -- 2.1 Interface for accessing the critical section -- 2.2 A program to test mutual exclusion -- 2.3 An attempt that violates mutual exclusion -- 2.4 An attempt that can deadlock -- 2.5 An attempt with strict alternation -- 2.6 Peterson's algorithm for mutual exclusion -- 2.7 Lamport's bakery algorithm -- 2.8 TestAndSet hardware instruction -- 2.9 Mutual exclusion using TestAndSet -- 2.10 Semantics of swap operation -- 2.11 Dekker.java -- 3.1 Binary semaphore -- 3.2 Counting semaphore -- 3.3 A shared buffer implemented with a circular array -- 3.4 Bounded buffer using semaphores -- 3.5 Producer-consumer algorithm using semaphores -- 3.6 Reader-writer algorithm using semaphores -- 3.7 The dining philosopher problem -- 3.8 Dining Philosopher -- 3.9 Resource Interface -- 3.10 Dining philosopher using semaphores -- 3.11 A pictorial view of a Java monitor -- 3.12 Bounded buffer monitor -- 3.13 Dining philosopher using monitors -- 3.14 Linked list -- 4.1 Concurrent histories illustrating sequential consistency -- 4.2 Sequential consistency does not satisfy locality -- 4.3 Summary of consistency conditions -- 5.1 Safe and unsafe read-write registers -- 5.2 Concurrent histories illustrating regularity -- 5.3 Atomic and nonatomic registers -- 5.4 Construction of a regular boolean register -- 5.5 Construction of a multivalued register -- 5.6 Construction of a multireader register -- 5.7 Construction of a multiwriter register -- 5.8 Lock-free atomic snapshot algorithm -- 5.9 Consensus Interface.

5.10 Impossibility of wait-free consensus with atomic read-write registers -- 5.11 TestAndSet class -- 5.12 Consensus using TestAndSet object -- 5.13 CompSwap object -- 5.14 Consensus using CompSwap object -- 5.15 Load-Linked and Store-Conditional object -- 5.16 Sequential queue -- 5.17 Concurrent queue -- 6.1 A datagram server -- 6.2 A datagram client -- 6.3 Simple name table -- 6.4 Name server -- 6.5 A client for name server -- 6.6 Topology class -- 6.7 Connector class -- 6.8 Message class -- 6.9 Linker class -- 6.10 Remote interface -- 6.11 A name service implementation -- 6.12 A RMI client program -- 7.1 An example of topology of a distributed system -- 7.2 A simple distributed program with two processes -- 7.3 A run in the happened-before model -- 7.4 A logical clock algorithm -- 7.5 A vector clock algorithm -- 7.6 The VCLinker class that extends the Linker class -- 7.7 A sample execution of the vector clock algorithm -- 7.8 A direct-dependency clock algorithm -- 7.9 A sample execution of the direct-dependency clock algorithm -- 7.10 The matrix clock algorithm -- 8.1 Testing a lock implementation -- 8.2 ListenerThread -- 8.3 Process.java -- 8.4 A centralized mutual exclusion algorithm -- 8.5 Lamport's mutual exclusion algorithm -- 8.6 Ricart and Agrawala's algorithm -- 8.7 (a) Conflict graph -- (b) an acyclic orientation with P2 and P4 as sources -- (c) orientation after P3 and P4 finish eating -- 8.8 An algorithm for dining philosopher problem -- 8.9 A token ring algorithm for the mutual exclusion problem -- 9.1 Consistent and inconsistent cuts -- 9.2 Classification of messages -- 9.3 Chandy and Lamport's snapshot algorithm -- 9.4 Linker extended for use with SenderCamera -- 9.5 A global snapshot algorithm based on sender recording -- 9.6 Invocation of the global snapshot algorithm.

10.1 WCP (weak conjunctive predicate) detection algorithm-checker process.