Design and Analysis of Distributed Algorithms

1. Auflage 2006
ISBN: 978-0-471-71997-7
Verlag: Wiley

Buch, Englisch, 608 Seiten, Format (B × H): 165 mm x 236 mm, Gewicht: 962 g

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.

Autoren/Hrsg.

Santoro, Nicola

Fachgebiete

• Mathematik | Informatik EDV | Informatik Programmierung | Softwareentwicklung Algorithmen & Datenstrukturen

Inhaltsverzeichnis

Preface xiv

1 Distributed Computing Environments 1
1.1 Entities 1
1.2 Communication 4
1.3 Axioms and Restrictions 4
1.4 Cost and Complexity 9
1.5 An Example: Broadcasting 10
1.6 States and Events 14
1.7 Problems and Solutions (*) 17
1.8 Knowledge 19
1.9 Technical Considerations 22
1.10 Summary of Definitions 25
1.11 Bibliographical Notes 25
1.12 Exercises, Problems, and Answers 26

2 Basic Problems And Protocols 29
2.1 Broadcast 29
2.2 Wake-Up 36
2.3 Traversal 41
2.4 Practical Implications: Use a Subnet 51
2.5 Constructing a Spanning Tree 52
2.6 Computations in Trees 70
2.7 Summary 89
2.8 Bibliographical Notes 90
2.9 Exercises, Problems, and Answers 91

3 Election 99
3.1 Introduction 99
3.2 Election in Trees 102
3.3 Election in Rings 104
3.4 Election in Mesh Networks 158
3.5 Election in Cube Networks 166
3.6 Election in Complete Networks 174
3.7 Election in Chordal Rings (?) 183
3.8 Universal Election Protocols 185
3.9 Bibliographical Notes 212
3.10 Exercises, Problems, and Answers 214

4 Message Routing and Shortest Paths 225
4.1 Introduction 225
4.2 Shortest Path Routing 226
4.3 Coping with Changes 253
4.4 Routing in Static Systems: Compact Tables 261
4.5 Bibliographical Notes 267
4.6 Exercises, Problems, and Answers 269

5 Distributed Set Operations 277
5.1 Introduction 277
5.2 Distributed Selection 279
5.3 Sorting a Distributed Set 297
5.4 Distributed Sets Operations 315
5.5 Bibliographical Notes 323
5.6 Exercises, Problems, and Answers 324

6 Synchronous Computations 333
6.1 Synchronous Distributed Computing 333
6.2 Communicators, Pipeline, and Transformers 343
6.3 Min-Finding and Election: Waiting and Guessing 360
6.4 Synchronization Problems: Reset, Unison, and Firing Squad 385
6.5 Bibliographical Notes 391
6.6 Exercises, Problems, and Answers 392

7 Computing in Presence of Faults 408
7.1 Introduction 408
7.2 The Crushing Impact of Failures 417
7.3 Localized Entity Failures: Using Synchrony 425
7.4 Localized Entity Failures: Using Randomization 443
7.5 Localized Entity Failures: Using Fault Detection 449
7.6 Localized Entity Failures: Pre-Execution Failures 454
7.7 Localized Link Failures 457
7.8 Ubiquitous Faults 467
7.9 Bibliographical Notes 486
7.10 Exercises, Problems, and Answers 488

8 Detecting Stable Properties 500
8.1 Introduction 500
8.2 Deadlock Detection 500
8.3 Global Termination Detection 518
8.4 Global Stable Property Detection 526
8.5 Bibliographical Notes 532CONTENTS xiii
8.6 Exercises, Problems, and Answers 534

9 Continuous Computations 541
9.1 Introduction 541
9.2 Keeping Virtual Time 542
9.3 Distributed Mutual Exclusion 549
9.4 Deadlock: System Detection and Resolution 566
9.5 Bibliographical Notes 569
9.6 Exercises, Problems, and Answers 570

Index 577

Über Autor(innen)

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.