Design and Analysis of Distributed Algorithms (Wiley Series on Parallel and

Design And Analyze algorithms for distributed computing environments Design and Analysis of Distributed Algorithms focuses on developing problem-solving skills and fully exploiting design tools and techniques. Moreover, the author helps readers develop the analytical tools and skills needed to evaluate the costs of complex designs and protocols. This text is based on a simple and fully reactive computational model that allows for intuitive comprehension and logical designs. The principles and techniques that users learn can be applied to any distributed computing environment (e.g., distributed systems, communication networks, data networks, grid networks, internet, etc.). Based on a method developed and refined during the author's twenty years of teaching experience, the text provides a wealth of unique material and learning aids that enable the reader to learn how to design algorithms and protocols to solve problems and perform tasks efficiently in a distributed computing environment. Features include: * Emphasis on developing problem-solving skills and fully leveraging design tools and techniques with a straightforward, easy-to-follow writing style * Chapter on distributed data and structures, an important area not covered in comparable texts * Detailed coverage of synchronous computations, a necessary element for "energy aware" computing * Theoretical and experimental exercises in each chapter that allow readers to apply their newfound skills All algorithms and protocols presented in the text, as well as those in the exercises, are easily and immediately programmable. References at the end of each chapter lead readers to additional materials for further study. A natural textbook for upper-level undergraduates and graduate students, with its emphasis on problem solving, this book is also ideal for system-protocol designers and communications software engineers and developers. It will enable them to understand the principles of how to design workable, efficient protocols in any distributed computing environment.

NICOLA SANTORO, PhD, is Professor of Computer Science at Carleton University. Dr. Santoro has been involved in distributed computing from the beginning of the field. He has contributed extensively on the algorithmic aspects, authoring many seminal papers. He is a founder of the main theoretical conferences in the field (PODC, DISC, SIROCCO). His current research is on distributed algorithms for mobile agents, autonomous mobile robots, and mobile sensor networks.

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.