Introduction to distributed self-stabilizing algorithms

Preface......Page 15
Acknowledgments......Page 19
 Parable of the Collatz Conjecture......Page 21
  Major Advantage: Fault Tolerance......Page 22
  Other Advantages......Page 24
  Relative Drawbacks and Alternatives......Page 25
  Expressiveness......Page 26
  Taxonomy of the Self-Stabilizing Literature......Page 27
 Roadmap of this Book......Page 29
  Graph Notions......Page 31
  Variables......Page 32
  Steps and Executions......Page 33
  Daemons......Page 34
 Self-Stabilization......Page 36
  Self-Stabilization and Silence......Page 37
  Time Complexity......Page 38
  Space Complexity......Page 41
 The Problem......Page 43
 The Algorithm......Page 44
  Partial Correctness......Page 45
  Termination......Page 46
  Time Complexity......Page 49
 The Algorithm......Page 53
  Closure and Correctness......Page 55
  Convergence and Complexity......Page 56
  Memory Requirement......Page 63
 Related Work......Page 64
 The Problem......Page 67
 The Algorithm......Page 68
  Partial Correctness......Page 71
  Termination......Page 73
  Time Complexity......Page 75
 The Problem......Page 81
 The Algorithm......Page 82
  Proof of Self-Stabilization......Page 85
  Complexity Analysis......Page 91
  Proof of Self-Stabilization......Page 102
  Complexity Analysis......Page 103
Hierarchical Collateral Composition......Page 109
  A Sufficient Condition......Page 111
 A Toy Example......Page 116
  Algorithm BFS......Page 117
  Algorithm STM......Page 118
  Algorithm INMAX......Page 121
 Hierarchical vs. Nonhierarchical Collateral Composition......Page 123
  Communication Links......Page 127
  Process Execution......Page 128
 Related Work......Page 129
  Silence in Message Passing......Page 131
  An Example......Page 132
  Memory Requirement......Page 133
  Message Passing Version of the Token Ring Algorithm of Dijkstra......Page 134
  Data-Link Protocol......Page 136
  From Atomic-State to Message Passing Model......Page 137
  Propagation of Information with Feedback (PIF)......Page 139
  A PIF-Based Universal Transformer......Page 142
 Stabilization Time in Message Passing......Page 145
Bibliography......Page 149
Authors' Biographies......Page 163
Index......Page 165
Blank Page......Page 2