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 P2 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

10.2 Circulating token with vector clock

10.3 An application that runs circulating token with a sensor

10.4 Monitor process algorithm at Pi

10.5 Token-based WCP detection algorithm

11.1 A diffusing computation for the shortest path

11.2 Interface for a termination detection algorithm

11.3 Termination detection algorithm

11.4 A diffusing computation for the shortest path with termination

11.5 Termination detection by token traversal

12.1 A FIFO computation that is not causally ordered

12.2 An algorithm for causal ordering of messages at Pi

12.3 Structure of a causal message

12.4 CausalLinker for causal ordering of messages

12.5 A chat program

12.6 A computation that is synchronously ordered

12.7 A computation that is not synchronously ordered

12.8 The algorithm at Pi for synchronous ordering of messages

12.9 The algorithm for synchronous ordering of messages

13.1 The leader election algorithm

13.2 Configurations for the worst case (a) and the best case (b)

13.3 A spanning tree construction algorithm

13.4 A convergecast algorithm

13.5 A broadcast algorithm

13.6 Algorithm for computing a global function

13.7 Computing the global sum

14.1 Algorithm for the simple synchronizer at Pj

14.2 Implementation of the simple synchronizer

14.3 An algorithm that generates a tree on an asynchronous network

14.4 BFS tree algorithm using a synchronizer

14.5 Alpha synchronizer

15.1 (a) Commutativity of disjoint events; (b) asynchrony of messages

15.2 (a) Case 1: proc(e)proc(f); (b) case 2: proc(e) = proc(f)

15.3 Algorithm at Pi for consensus under crash failures

15.4 Consensus in a synchronous environment

15.5 Consensus tester

15.6 An algorithm for Byzantine General Agreement

16.1 Algorithm for the coordinator of the two-phase commit protocol

16.2 Algorithm for the participants in the two-phase commit protocol

17.1 An example of the domino effect

17.2 Examples of zigzag paths

17.3 A distributed computation

17.4 Formal description of the fault-tolerant vector clock

17.5 Formal description of the version end-table mechanism

17.6 An optimistic protocol for asynchronous recovery

18.1 K-state self-stabilizing algorithm

18.2 A move by the bottom machine in the K-state algorithm

18.3 A move by a normal machine in the K-state algorithm

18.4 Self-stabilizing algorithm for mutual exclusion in a ring for the bottom machine

18.5 Self-stabilizing algorithm for mutual exclusion in a ring for a normal machine

18.6 Self-stabilizing algorithm for (BFS) spanning tree

18.7 Self-stabilizing spanning tree algorithm for the root

18.8 Self-stabilizing spanning tree algorithm for nonroot nodes

18.9 A Java program for spanning tree

A.1 Util.java

A.2 Symbols.java

A.3 Matrix.java

A.4 MsgList.java.

A.5 IntLinkedList.java

A.6 PortAddr.java

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset
3.14.145.128