Self-stabilizationMIT Press, 2000 - 197 Seiten Self-stabilization, an important concept to theoreticians and practitioners in distributed computing and communication networks, refers to a system's ability to recover automatically from unexpected faults. In this book Shlomi Dolev presents the fundamentals of self-stabilization and demonstrates the process of designing self-stabilizing distributed systems. He details the algorithms that can be started in an arbitrary state, allowing the system to recover from the faults that brought it to that state. The book proceeds from the basic concept of self-stabilizing algorithms to advanced applications. |
Inhalt
Introduction | 1 |
Definitions Techniques and Paradigms | 5 |
22 SelfStabilization Requirements | 9 |
24 Randomized SelfStabilization | 11 |
SpanningTree Construction | 12 |
Mutual Exclusion | 16 |
27 Fair Composition of SelfStabilizing Algorithms | 22 |
28 Recomputation of Floating Output | 27 |
Converting Synchronous to Asynchronous Algorithms | 98 |
Converting Idbased to Uniform Dynamic Systems | 110 |
Stabilizers | 121 |
52 Monitoring and Resetting | 123 |
Convergence in the Presence of Faults | 135 |
61 Digital Clock Synchronization | 137 |
62 Stabilization in Spite of Napping | 142 |
63 Stabilization in Spite of Byzantine Faults | 146 |
29 Proof Techniques | 31 |
210 PseudoSelfStabilization | 45 |
Motivating SelfStabilization | 57 |
32 Arbitrary Configuration Because of Crashes | 61 |
33 Frequently Asked Questions | 66 |
SelfStabilizing Algorithms for Model Conversions | 71 |
Converting Shared Memory to Message Passing | 73 |
Converting an Idbased System to a Specialprocessor System | 87 |
Converting a Special Processor to an Idbased Dynamic System | 90 |
64 Stabilization in the Presence of Faults in Asynchronous Systems | 155 |
Local Stabilization | 159 |
72 SelfStabilizing FaultContaining Algorithms | 164 |
73 ErrorDetection Codes and Repair | 168 |
SelfStabilizing Computing | 173 |
82 Queue Machine | 181 |
References | 187 |
| 193 | |
Andere Ausgaben - Alle anzeigen
Häufige Begriffe und Wortgruppen
abstract task algorithm presented arbitrary configuration assigns assume asynchronous systems bits c₁ central daemon cessor changes the value chooses clock value color communication graph communication registers computation step configuration is reached convergence counter crash critical section cycles data-link algorithm defined Dijkstra's algorithm distance distributed algorithm Distributed Computing distributed systems Dolev ensure error-detection code execution that starts exists failure detector fair execution faulty processors floating output forall frame holds identifier infinitely initial input label leader election LEMMA message passing mutual exclusion algorithm neighboring processors network layer non-faulty processors number of processors number of rounds P₁ phase variable possible presented in section processor executes processor Pi proof pulse qs,r queue randomized algorithm reaches a safe ReadSet repeatedly rithm root safe configuration self-stabilizing algorithm sender receives sequence spanning tree spanning-tree special processor stabilizing superstabilizing technique timeout token token-passing topology transient fault tuple Turing machine update algorithm write operation
Verweise auf dieses Buch
Self-Stabilizing Systems: 5th International Workshop, WSS 2001 ..., Band 5 Ajoy K. Datta Keine Leseprobe verfügbar - 2001 |
Distributed Sensor Networks: A Multiagent Perspective Victor Lesser,Charles L. Ortiz,Milind Tambe Eingeschränkte Leseprobe - 2003 |