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

This text is based on a simple and fully reactive computational model that allows for intuitive comprehension and logical designs. The principles and techniques presented can be applied to any distributed computing environment (e.g., distributed systems, communication networks, data networks, grid networks, internet, etc.). The text provides a wealth of unique material for learning how to design algorithms and protocols perform tasks efficiently in a distributed computing environment.

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.

CONTENTS......Page 10 PREFACE......Page 18 1.1 ENTITIES......Page 22 1.3 AXIOMS AND RESTRICTIONS......Page 25 1.4 COST AND COMPLEXITY......Page 30 1.6 STATES AND EVENTS......Page 35 1.7 PROBLEMS AND SOLUTIONS (
)......Page 38 1.9 TECHNICAL CONSIDERATIONS......Page 43 2.1 BROADCAST......Page 50 2.2 WAKE-UP......Page 57 2.3 TRAVERSAL......Page 62 2.4 PRACTICAL IMPLICATIONS: USE A SUBNET......Page 72 2.5 CONSTRUCTING A SPANNING TREE......Page 73 2.5.2 Other SPT Constructions with Single Initiator......Page 79 2.6 COMPUTATIONS IN TREES......Page 91 2.6.3 Distributed Function Evaluation......Page 97 2.6.7 Computing in Rooted Trees......Page 106 2.7 SUMMARY......Page 110 2.8 BIBLIOGRAPHICAL NOTES......Page 111 CHAPTER 3......Page 120 3.2 ELECTION IN TREES......Page 123 3.3 ELECTION IN RINGS......Page 125 3.4 ELECTION IN MESH NETWORKS......Page 179 3.5 ELECTION IN CUBE NETWORKS......Page 187 3.6 ELECTION IN COMPLETE NETWORKS......Page 195 3.6.3 Harvesting the Communication Power......Page 201 3.8 UNIVERSAL ELECTION PROTOCOLS......Page 206 CHAPTER 4......Page 246 4.3 COPING WITH CHANGES......Page 274 4.3.3 On Correctness and Guarantees......Page 280 4.4 ROUTING IN STATIC SYSTEMS: COMPACT TABLES......Page 282 5.1 INTRODUCTION......Page 298 CHAPTER 6......Page 354 6.3.3 Double Wait: Integrating Waiting and Guessing......Page 399 CHAPTER 7......Page 429 7.3 LOCALIZED ENTITY FAILURES: USING SYNCHRONY......Page 446 7.4 LOCALIZED ENTITY FAILURES: USING RANDOMIZATION......Page 464 7.6 LOCALIZED ENTITY FAILURES: PREEXECUTION FAILURES......Page 475 CHAPTER 8......Page 521 CHAPTER 9......Page 562 "Design and Analysis of Distributed Algorithms focuses on developing problem-solving skills and fully exploiting design tools and techniques. Moreoever, the author helps readers develop the analytical tools and skills needed to evaluate the costs of complex designs and protocols." "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."--Jacket