| |
| |
| Preface | |
| |
| |
| |
| Distributed Computing Environments | |
| |
| |
| |
| Entities | |
| |
| |
| |
| Communication | |
| |
| |
| |
| Axioms and Restrictions | |
| |
| |
| |
| Axioms | |
| |
| |
| |
| Restrictions | |
| |
| |
| |
| Cost and Complexity | |
| |
| |
| |
| Amount of Communication Activities | |
| |
| |
| |
| Time | |
| |
| |
| |
| An Example: Broadcasting | |
| |
| |
| |
| States and Events | |
| |
| |
| |
| Time and Events | |
| |
| |
| |
| States and Configurations | |
| |
| |
| |
| Problems and Solutions (* | |
| |
| |
| |
| Knowledge | |
| |
| |
| |
| Levels of Knowledge | |
| |
| |
| |
| Types of Knowledge | |
| |
| |
| |
| Technical Considerations | |
| |
| |
| |
| Messages | |
| |
| |
| |
| Protocol | |
| |
| |
| |
| Communication Mechanism | |
| |
| |
| |
| Summary of Definitions | |
| |
| |
| |
| Bibliographical Notes | |
| |
| |
| |
| Exercises, Problems, and Answers | |
| |
| |
| |
| Exercises and Problems | |
| |
| |
| |
| Answers to Exercises | |
| |
| |
| |
| Basic Problems And Protocols | |
| |
| |
| |
| Broadcast | |
| |
| |
| |
| The Problem | |
| |
| |
| |
| Cost of Broadcasting | |
| |
| |
| |
| Broadcasting in Special Networks | |
| |
| |
| |
| Wake-Up | |
| |
| |
| |
| Generic Wake-Up | |
| |
| |
| |
| Wake-Up in Special Networks | |
| |
| |
| |
| Traversal | |
| |
| |
| |
| Depth-First Traversal | |
| |
| |
| |
| Hacking (* | |
| |
| |
| |
| Traversal in Special Networks | |
| |
| |
| |
| Considerations on Traversal | |
| |
| |
| |
| Practical Implications: Use a Subnet | |
| |
| |
| |
| Constructing a Spanning Tree | |
| |
| |
| |
| SPT Construction with a Single Initiator: Shout | |
| |
| |
| |
| Other SPT Constructions with Single Initiator | |
| |
| |
| |
| Considerations on the Constructed Tree | |
| |
| |
| |
| Application: Better Traversal | |
| |
| |
| |
| Spanning-Tree Construction with Multiple Initiators | |
| |
| |
| |
| Impossibility Result | |
| |
| |
| |
| SPT with Initial Distinct Values | |
| |
| |
| |
| Computations in Trees | |
| |
| |
| |
| Saturation: A Basic Technique | |
| |
| |
| |
| Minimum Finding | |
| |
| |
| |
| Distributed Function Evaluation | |
| |
| |
| |
| Finding Eccentricities | |
| |
| |
| |
| Center Finding | |
| |
| |
| |
| Other Computations | |
| |
| |
| |
| Computing in Rooted Trees | |
| |
| |
| |
| Summary | |
| |
| |
| |
| Summary of Problems | |
| |
| |
| |
| Summary of Techniques | |
| |
| |
| |
| Bibliographical Notes | |
| |
| |
| |
| Exercises, Problems, and Answers | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Problems | |
| |
| |
| |
| Answers to Exercises | |
| |
| |
| |
| Election | |
| |
| |
| |
| Introduction | |
| |
| |
| |
| Impossibility Result | |
| |
| |
| |
| Additional Restrictions | |
| |
| |
| |
| Solution Strategies | |
| |
| |
| |
| Election in Trees | |
| |
| |
| |
| Election in Rings | |
| |
| |
| |
| All the Way | |
| |
| |
| |
| As Far As It Can | |
| |
| |
| |
| Controlled Distance | |
| |
| |
| |
| Electoral Stages | |
| |
| |
| |
| Stages with Feedback | |
| |
| |
| |
| Alternating Steps | |
| |
| |
| |
| Unidirectional Protocols | |
| |
| |
| |
| Limits to Improvements (* | |
| |
| |
| |
| Summary and Lessons | |
| |
| |
| |
| Election in Mesh Networks | |
| |
| |
| |
| Meshes | |
| |
| |
| |
| Tori | |
| |
| |
| |
| Election in Cube Networks | |
| |
| |
| |
| Oriented Hypercubes | |
| |
| |
| |
| Unoriented Hypercubes | |
| |
| |
| |
| Election in Complete Networks | |
| |
| |
| |
| Stages and Territory | |
| |
| |
| |
| Surprising Limitation | |
| |
| |
| |
| Harvesting the Communication Power | |
| |
| |
| |
| Election in Chordal Rings (* | |
| |
| |
| |
| Chordal Rings | |
| |
| |
| |
| Lower Bounds | |
| |
| |
| |
| Universal Election Protocols | |
| |
| |
| |
| Mega-Merger | |
| |
| |
| |
| Analysis of Mega-Merger | |
| |
| |
| |
| YO-YO | |
| |
| |
| |
| Lower Bounds and Equivalences | |
| |
| |
| |
| Bibliographical Notes | |
| |
| |
| |
| Exercises, Problems, and Answers | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Problems | |
| |
| |
| |
| Answers to Exercises | |
| |
| |
| |
| Message Routing and Shortest Paths | |
| |
| |
| |
| Introduction | |
| |
| |
| |
| Shortest Path Routing | |
| |
| |
| |
| Gossiping the Network Maps | |
| |
| |
| |
| Iterative Construction of Routing Tables | |
| |
| |
| |
| Constructing Shortest-Path Spanning Tree | |
| |
| |
| |
| Constructing All-Pairs Shortest Paths | |
| |
| |
| |
| Min-Hop Routing | |
| |
| |
| |
| Suboptimal Solutions: Routing Trees | |
| |
| |
| |
| Coping with Changes | |
| |
| |
| |
| Adaptive Routing | |
| |
| |
| |
| Fault-Tolerant Tables | |
| |
| |
| |
| On Correctness and Guarantees | |
| |
| |
| |
| Routing in Static Systems: Compact Tables | |
| |
| |
| |
| The Size of Routing Tables | |
| |
| |
| |
| Interval Routing | |
| |
| |
| |
| Bibliographical Notes | |
| |
| |
| |
| Exercises, Problems, and Answers | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Problems | |
| |
| |
| |
| Answers to Exercises | |
| |
| |
| |
| Distributed Set Operations | |
| |
| |
| |
| Introduction | |
| |
| |
| |
| Distributed Selection | |
| |
| |
| |
| Order Statistics | |
| |
| |
| |
| Selection in a Small Data Set | |
| |
| |
| |
| Simple Case: Selection Among Two Sites | |
| |
| |
| |
| General Selection Strategy: RankSelect | |
| |
| |
| |
| Reducing the Worst Case: ReduceSelect | |
| |
| |
| |
| Sorting a Distributed Set | |
| |
| |
| |
| Distributed Sorting | |
| |
| |
| |
| Special Case: Sorting on a Ordered Line | |
| |
| |
| |
| Removing the Topological Constraints: Complete Graph | |
| |
| |
| |
| Basic Limitations | |
| |
| |
| |
| Efficient Sorting: SelectSort | |
| |
| |
| |
| Unrestricted Sorting | |
| |
| |
| |
| Distributed Sets Operations | |
| |
| |
| |
| Operations on Distributed Sets | |
| |
| |
| |
| Local Structure | |
| |
| |
| |
| Local Evaluation (* | |
| |
| |
| |
| Global Evaluation | |
| |
| |
| |
| Operational Costs | |
| |
| |
| |
| Bibliographical Notes | |
| |
| |
| |
| Exercises, Problems, and Answers | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Problems | |
| |
| |
| |
| Answers to Exercises | |
| |
| |
| |
| Synchronous Computations | |
| |
| |
| |
| Synchronous Distributed Computing | |
| |
| |
| |
| Fully Synchronous Systems | |
| |
| |
| |
| Clocks and Unit of Time | |
| |
| |
| |
| Communication Delays and Size of Messages | |
| |
| |
| |
| On the Unique Nature of Synchronous Computations | |
| |
| |
| |
| The Cost of Synchronous Protocols | |
| |
| |
| |
| Communicators, Pipeline, and Transformers | |
| |
| |
| |
| Two-Party Communication | |
| |
| |
| |
| Pipeline | |
| |
| |
| |
| Transformers | |
| |
| |
| |
| Min-Finding and Election: Waiting and Guessing | |
| |
| |
| |
| Waiting | |
| |
| |
| |
| Guessing | |
| |
| |
| |
| Double Wait: Integrating Waiting and Guessing | |
| |
| |
| |
| Synchronization Problems: Reset, Unison, and Firing Squad | |
| |
| |
| |
| Reset /Wake-up | |
| |
| |
| |
| Unison | |
| |
| |
| |
| Firing Squad | |
| |
| |
| |
| Bibliographical Notes | |
| |
| |
| |
| Exercises, Problems, and Answers | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Problems | |
| |
| |
| |
| Answers to Exercises | |
| |
| |
| |
| Computing in Presence of Faults | |
| |
| |
| |
| Introduction | |
| |
| |
| |
| Faults and Failures | |
| |
| |
| |
| Modelling Faults | |
| |
| |
| |
| Topological Factors | |
| |
| |
| |
| Fault Tolerance, Agreement, and Common Knowledge | |
| |
| |
| |
| The Crushing Impact of Failures | |
| |
| |
| |
| Node Failures: Single-Fault Disaster | |
| |
| |
| |
| Consequences of the Single Fault Disaster | |
| |
| |
| |
| Localized Entity Failures: Using Synchrony | |
| |
| |
| |
| Synchronous Consensus with Crash Failures | |
| |
| |
| |
| Synchronous Consensus with Byzantine Failures | |
| |
| |
| |
| Limit to Number of Byzantine Entities for Agreement | |
| |
| |
| |
| From Boolean to General Byzantine Agreement | |
| |
| |
| |
| Byzantine Agreement in Arbitrary Graphs | |
| |
| |
| |
| Localized Entity Failures: Using Randomization | |
| |
| |
| |
| Random Actions and Coin Flips | |
| |
| |
| |
| Randomized Asynchronous Consensus: Crash Failures | |
| |
| |
| |
| Concluding Remarks | |
| |
| |
| |
| Localized Entity Failures: Using Fault Detection | |
| |
| |
| |
| Failure Detectors and Their Properties | |
| |
| |
| |
| The Weakest Failure Detector | |
| |
| |
| |
| Localized Entity Failures: Pre-Execution Failures | |
| |
| |
| |
| Partial Reliability | |
| |
| |
| |
| Example: Election in Complete Network | |
| |
| |
| |
| Localized Link Failures | |
| |
| |
| |
| A Tale of Two Synchronous Generals | |
| |
| |
| |
| Computing With Faulty Links | |
| |
| |
| |
| Concluding Remarks | |
| |
| |
| |
| Considerations on Localized Entity Failures | |
| |
| |
| |
| Ubiquitous Faults | |
| |
| |
| |
| Communication Faults and Agreement | |
| |
| |
| |
| Limits to Number of Ubiquitous Faults for Majority | |
| |
| |
| |
| Unanimity in Spite of Ubiquitous Faults | |
| |
| |
| |
| Tightness | |
| |
| |
| |
| Bibliographical Notes | |
| |
| |
| |
| Exercises, Problems, and Answers | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Problems | |
| |
| |
| |
| Answers to Exercises | |
| |
| |
| |
| Detecting Stable Properties | |
| |
| |
| |
| Introduction | |
| |
| |
| |
| Deadlock Detection | |
| |
| |
| |
| Deadlock | |
| |
| |
| |
| Detecting Deadlock: Wait-for Graph | |
| |
| |
| |
| Single-Request Systems | |
| |
| |
| |
| Multiple-Requests Systems | |
| |
| |
| |
| Dynamic Wait-for Graphs | |
| |
| |
| |
| Other Requests Systems | |
| |
| |
| |
| Global Termination Detection | |
| |
| |
| |
| A Simple Solution: Repeated Termination Queries | |
| |
| |
| |
| Improved Protocols: Shrink | |
| |
| |
| |
| Concluding Remarks | |
| |
| |
| |
| Global Stable Property Detection | |
| |
| |
| |
| General Strategy | |
| |
| |
| |
| Time Cuts and Consistent Snapshots | |
| |
| |
| |
| Computing A Consistent Snapshot | |
| |
| |
| |
| Summary: Putting All Together | |
| |
| |
| |
| Bibliographical Notes | |
| |
| |
| |
| Exercises, Problems, and Answers | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Problems | |
| |
| |
| |
| Answers to Exercises | |
| |
| |
| |
| Continuous Computations | |
| |
| |
| |
| Introduction | |
| |
| |
| |
| Keeping Virtual Time | |
| |
| |
| |
| Virtual Time and Causal Order | |
| |
| |
| |
| Causal Order: Counter Clocks | |
| |
| |
| |
| Complete Causal Order: Vector Clocks | |
| |
| |
| |
| Concluding Remarks | |
| |
| |
| |
| Distributed Mutual Exclusion | |
| |
| |
| |
| The Problem | |
| |
| |
| |
| A Simple And Efficient Solution | |
| |
| |
| |
| Traversing the Network | |
| |
| |
| |
| Managing a Distributed Queue | |
| |
| |
| |
| Decentralized Permissions | |
| |
| |
| |
| Mutual Exclusion in Complete Graphs: Quorum | |
| |
| |
| |
| Concluding Remarks | |
| |
| |
| |
| Deadlock: System Detection and Resolution | |
| |
| |
| |
| System Detection and Resolution | |
| |
| |
| |
| Detection and Resolution in Single-Request Systems | |
| |
| |
| |
| Detection and Resolution in Multiple-Requests Systems | |
| |
| |
| |
| Bibliographical Notes | |
| |
| |
| |
| Exercises, Problems, and Answers | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Problems | |
| |
| |
| |
| Answers to Exercises | |
| |
| |
| Index | |