Design and Analysis of Distributed Algorithms

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 styleChapter on distributed data and structures, an important area not covered in comparable textsDetailed coverage of synchronous computations, a necessary element for "energy aware" computingTheoretical 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.

Spis treści:
Preface.
1. Distributed Computing Environments.
1.1 Entities.
1.2 Communication.
1.3 Axioms and Restrictions.
1.3.1 Axioms.
1.3.2 Restrictions.
1.4 Cost and Complexity.
1.4.1 Amount of Communication Activities.
1.4.2 Time.
1.5 An Example: Broadcasting.
1.6 States and Events.
1.6.1 Time and Events.
1.6.2 States and Configurations.
1.7 Problems and Solutions (∗).
1.8 Knowledge.
1.8.1 Levels of Knowledge.
1.8.2 Types of Knowledge.
1.9 Technical Considerations.
1.9.1 Messages.
1.9.2 Protocol.
1.9.3 Communication Mechanism.
1.10 Summary of Definitions.
1.11 Bibliographical Notes.
1.12 Exercises, Problems, and Answers.
1.12.1 Exercises and Problems.
1.12.2 Answers to Exercises.
2. Basic Problems And Protocols.
2.1 Broadcast.
2.1.1 The Problem.
2.1.2 Cost of Broadcasting.
2.1.3 Broadcasting in Special Networks.
2.2 Wake–Up.
2.2.1 Generic Wake–Up.
2.2.2 Wake–Up in Special Networks.
2.3 Traversal.
2.3.1 Depth–First Traversal.
2.3.2 Hacking (∗).
2.3.3 Traversal in Special Networks.
2.3.4 Considerations on Traversal.
2.4 Practical Implications: Use a Subnet.
2.5 Constructing a Spanning Tree.
2.5.1 SPT Construction with a Single Initiator: Shout.
2.5.2 Other SPT Constructions with Single Initiator.
2.5.3 Considerations on the Constructed Tree.
2.5.4 Application: Better Traversal.
2.5.5 Spanning–Tree Construction with Multiple Initiators.
2.5.6 Impossibility Result.
2.5.7 SPT with Initial Distinct Values.
2.6 Computations in Trees.
2.6.1 Saturation: A Basic Technique.
2.6.2 Minimum Finding.
2.6.3 Distributed Function Evaluation.
2.6.4 Finding Eccentricities.
2.6.5 Center Finding.
2.6.6 Other Computations.
2.6.7 Computing in Rooted Trees.
2.7 Summary.
2.7.1 Summary of Problems.
2.7.2 Summary of Techniques.
2.8 Bibliographical Notes.
2.9 Exercises, Problems, and Answers.
2.9.1 Exercises.
2.9.2 Problems.
2.9.3 Answers to Exercises.
3. Election.
3.1 Introduction.
3.1.1 Impossibility Result.
3.1.2 Additional Restrictions.
3.1.3 Solution Strategies.
3.2 Election in Trees.
3.3 Election in Rings.
3.3.1 All the Way.
3.3.2 As Far As It Can.
3.3.3 Controlled Distance.
3.3.4 Electoral Stages.
3.3.5 Stages with Feedback.
3.3.6 Alternating Steps.
3.3.7 Unidirectional Protocols.
3.3.8 Limits to Improvements (∗).
3.3.9 Summary and Lessons.
3.4 Election in Mesh Networks.
3.4.1 Meshes.
3.4.2 Tori.
3.5 Election in Cube Networks.
3.5.1 Oriented Hypercubes.
3.5.2 Unoriented Hypercubes.
3.6 Election in Complete Networks.
3.6.1 Stages and Territory.
3.6.2 Surprising Limitation.
3.6.3 Harvesting the Communication Power.
3.7 Election in Chordal Rings (∗).
3.7.1 Chordal Rings.
3.7.2 Lower Bounds.
3.8 Universal Election Protocols.
3.8.1 Mega–Merger.
3.8.2 Analysis of Mega–Merger.
3.8.3 YO–YO.
3.8.4 Lower Bounds and Equivalences.
3.9 Bibliographical Notes.
3.10 Exercises, Problems, and Answers.
3.10.1 Exercises.
3.10.2 Problems.
3.10.3 Answers to Exercises.
4. Message Routing and Shortest Paths.
4.1 Introduction.
4.2 Shortest Path Routing.
4.2.1 Gossiping the Network Maps.
4.2.2 Iterative Construction of Routing Tables.
4.2.3 Constructing Shortest–Path Spanning Tree.
4.2.4 Constructing All–Pairs Shortest Paths.
4.2.5 Min–Hop Routing.
4.2.6 Suboptimal Solutions: Routing Trees.
4.3 Coping with Changes.
4.3.1 Adaptive Routing.
4.3.2 Fault–Tolerant Tables.
4.3.3 On Correctness and Guarantees.
4.4 Routing in Static Systems: Compact Tables.
4.4.1 The Size of Routing Tables.
4.4.2 Interval Routing.
4.5 Bibliographical Notes.
4.6 Exercises, Problems, and Answers.
4.6.1 Exercises.
4.6.2 Problems.
4.6.3 Answers to Exercises.
5. Distributed Set Operations.
5.1 Introduction.
5.2 Distributed Selection.
5.2.1 Order Statistics.
5.2.2 Selection in a Small Data Set.
5.2.3 Simple Case: Selection Among Two Sites.
5.2.4 General Selection Strategy: RankSelect.
5.2.5 Reducing the Worst Case: ReduceSelect.
5.3 Sorting a Distributed Set.
5.3.1 Distributed Sorting.
5.3.2 Special Case: Sorting on a Ordered Line.
5.3.3 Removing the Topological Constraints: Complete Graph.
5.3.4 Basic Limitations.
5.3.5 Efficient Sorting: SelectSort.
5.3.6 Unrestricted Sorting.
5.4 Distributed Sets Operations.
5.4.1 Operations on Distributed Sets.
5.4.2 Local Structure.
5.4.3 Local Evaluation (∗).
5.4.4 Global Evaluation.
5.4.5 Operational Costs.
5.5 Bibliographical Notes.
5.6 Exercises, Problems, and Answers.
5.6.1 Exercises.
5.6.2 Problems.
5.6.3 Answers to Exercises.
6. Synchronous Computations.
6.1 Synchronous Distributed Computing.
6.1.1 Fully Synchronous Systems.
6.1.2 Clocks and Unit of Time.
6.1.3 Communication Delays and Size of Messages.
6.1.4 On the Unique Nature of Synchronous Computations.
6.1.5 The Cost of Synchronous Protocols.
6.2 Communicators, Pipeline, and Transformers.
6.2.1 Two–Party Communication.
6.2.2 Pipeline.
6.2.3 Transformers.
6.3 Min–Finding and Election: Waiting and Guessing.
6.3.1 Waiting.
6.3.2 Guessing.
6.3.3 Double Wait: Integrating Waiting and Guessing.
6.4 Synchronization Problems: Reset, Unison, and Firing Squad.
6.4.1