1. Edition - November 2006
129.- Euro
2006. 608 Pages, Hardcover
ISBN-10: 0-471-71997-8
ISBN-13: 978-0-471-71997-7 - John Wiley & Sons






Sample Chapter

Short description
This graduate textbook and professional reference for designers and researchers focuses on the design and analysis of distributed algorithms and protocols. Concentrating on teaching problem solving, Design and Analysis of Distributed Algorithms includes essential new material such as Synchronous Computations (necessary for "energy-aware" computing), Structural Knowledge and Communication Complexity, and numerous exercises and solutions immediately programmable.

From the contents
Preface.

1. Distributed Computing Environments.

1.1 Entities.

1.2 Communication.

1.3 Axioms and Restrictions.

1.4 Cost and Complexity.

1.5 An Example: Broadcasting.

1.6 States and Events.

1.7 Problems and Solutions (*).

1.8 Knowledge.

1.9 Technical Considerations.

1.10 Summary of Definitions.

1.11 Bibliographical Notes.

1.12 Exercises, Problems, and Answers.

2. Basic Problems And Protocols.

2.1 Broadcast.

2.2 Wake-Up.

2.3 Traversal.

2.4 Practical Implications: Use a Subnet.

2.5 Constructing a Spanning Tree.

2.6 Computations in Trees.

2.7 Summary.

2.8 Bibliographical Notes.

2.9 Exercises, Problems, and Answers.

3. Election.

3.1 Introduction.

3.2 Election in Trees.

3.3 Election in Rings.

3.4 Election in Mesh Networks.

3.5 Election in Cube Networks.

3.6 Election in Complete Networks.

3.7 Election in Chordal Rings (*).

3.8 Universal Election Protocols.

3.9 Bibliographical Notes.

3.10 Exercises, Problems, and Answers.

4. Message Routing and Shortest Paths.

4.1 Introduction.

4.2 Shortest Path Routing.

4.3 Coping with Changes.

4.4 Routing in Static Systems: Compact Tables.

4.5 Bibliographical Notes.

4.6 Exercises, Problems, and Answers.

5. Distributed Set Operations.

5.1 Introduction.

5.2 Distributed Selection.

5.3 Sorting a Distributed Set.

5.4 Distributed Sets Operations.

5.5 Bibliographical Notes.

5.6 Exercises, Problems, and Answers.

6. Synchronous Computations.

6.1 Synchronous Distributed Computing.

6.2 Communicators, Pipeline, and Transformers.

6.3 Min-Finding and Election: Waiting and Guessing.

6.4 Synchronization Problems: Reset, Unison, and Firing Squad.

6.5 Bibliographical Notes.

6.6 Exercises, Problems, and Answers.

7. Computing in Presence of Faults.

7.1 Introduction.

7.2 The Crushing Impact of Failures.

7.3 Localized Entity Failures: Using Synchrony.

7.4 Localized Entity Failures: Using Randomization.

7.5 Localized Entity Failures: Using Fault Detection.

7.6 Localized Entity Failures: Pre-Execution Failures.

7.7 Localized Link Failures.

7.8 Ubiquitous Faults.

7.9 Bibliographical Notes.

7.10 Exercises, Problems, and Answers.

8. Detecting Stable Properties.

8.1 Introduction.

8.2 Deadlock Detection.

8.3 Global Termination Detection.

8.4 Global Stable Property Detection.

8.5 Bibliographical Notes.

8.6 Exercises, Problems, and Answers.

9. Continuous Computations.

9.1 Introduction.

9.2 Keeping Virtual Time.

9.3 Distributed Mutual Exclusion.

9.4 Deadlock: System Detection and Resolution.

9.5 Bibliographical Notes.

9.6 Exercises, Problems, and Answers.

Index.