Structural Failure Models for Fault-Tolerant Distributed Computing

✍ Scribed by Timo Warns

• Publisher: Vieweg and Teubner
• Year: 2010
• Tongue: English
• Leaves: 233
• Series: Software Engineering Research
• Edition: 2010
• Category: Library

✦ Synopsis

Given that faults cannot be prevented in sufficiently complex systems, means of fault tolerance are essential for dependable distributed systems. Designing and evaluating fault-tolerant systems require well-conceived fault models. In the past, theoretical works have used simplified models that, while being tractable, turned out to be inaccurate. Practical works have used probabilistic fault models that, while being more accurate, often turned out to be intractable. Timo Warns bridges the gap between theory and practice regarding fault models. He has developed tractable fault models that, while being non-probabilistic, are accurate for dependent and propagating faults. Using seminal problems such as consensus and constructing coteries, he demonstrates how the new models can be used to design and evaluate effective and efficient means of fault tolerance.

✦ Table of Contents

Cover......Page 1
Software Engineering Research......Page 3
Structural Failure Models
for Fault-Tolerant
Distributed Computing......Page 4
ISBN 9783834812872......Page 5
Foreword......Page 7
Acknowledgments......Page 8
Abstract......Page 10
Zusammenfassung......Page 12
Contents......Page 14
List of Figures and Tables......Page 16
1.1 Motivation......Page 18
1.3 Outline......Page 22
1.4 Remarks on Notation......Page 25
2 Modelling Fault-Tolerant Distributed Systems......Page 26
2.1 Interprocess Communication......Page 27
2.2 States, Traces, Properties......Page 29
2.3 Temporal Logic of Actions......Page 36
2.4 Fault Model......Page 42
2.5 Fault Tolerance......Page 46
2.6 Timing Model......Page 48
2.7 Summary......Page 54
3 Modelling Fault Assumptions with Structural Failure Models......Page 56
3.1 Related Work......Page 57
3.2 Functional Failure Models......Page 59
3.3 Structural Failure Models......Page 64
3.4 Component Failure Models......Page 67
3.4.1 Process Failure Models......Page 68
3.4.2 Channel Failure Models......Page 72
3.4.3 Hybrid Failure Models......Page 75
3.5 Set-Based Structural Failure Models......Page 77
3.5.1 Dependent Faults......Page 78
3.5.2 Set-Based Structural Failure Models......Page 80
3.5.3 Threshold Assumptions and Dependent Faults......Page 89
3.5.4 Classes of Set-Based Structural Failure Models......Page 91
3.6 Sequence-Based Structural Failure Models......Page 106
3.7 Stochastics, Sets, and Sequences......Page 109
3.8 Summary......Page 111
4 Constructing Coteries......Page 114
4.1 Related Work......Page 116
4.2 Introduction to Quorums......Page 118
4.3 Highly Available Static Coteries......Page 126
4.4 Highly Available Dynamic Coteries......Page 135
4.5 Reducing Probe Complexity......Page 143
4.6 Summary......Page 154
5 Reaching Consensus......Page 156
5.1 Related Work......Page 158
5.2.1 Specifying Consensus......Page 160
5.2.2 The FLP Impossibility Result......Page 164
5.2.3 Principles of Solving Consensus......Page 165
5.2.4 Quality of Consensus Algorithms......Page 167
5.3 Consensus in Asynchronous Systems with Unreliable Failure Detectors......Page 171
5.3.1 A Versatile Consensus Algorithm......Page 172
5.3.2 Adversary Structures......Page 176
5.3.3 Didep Models......Page 179
5.4 Consensus in Partially Synchronous Systems......Page 186
5.5 Consensus in Synchronous Systems......Page 191
5.6 Summary......Page 203
6 Conclusion and Future Work......Page 206
Bibliography......Page 212
Index......Page 230