Structural Failure Models for Fault-Tolerant Distributed Computing (eBook)

Timo Warns (Autor)

eBook Download: PDF

2011 | 2010
XV, 216 Seiten
Vieweg & Teubner (Verlag)
978-3-8348-9707-7 (ISBN)

Infos

Timo Warns 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.

Dr. Timo Warns completed his doctoral thesis under the supervision of Prof. Dr. Wilhelm Hasselbring at the Carl von Ossietzky University of Oldenburg.

Inhalt

Foreword 6
Acknowledgments 7
Abstract 9
Zusammenfassung 11
Contents 13
List of Figures and Tables 15
1 Introduction 16
1.1 Motivation 16
1.2 Objectives 20
1.3 Outline 20
1.4 Remarks on Notation 23
2 Modelling Fault-Tolerant Distributed Systems 24
2.1 Interprocess Communication 25
2.2 States, Traces, Properties 27
2.3 Temporal Logic of Actions 34
2.4 Fault Model 40
2.5 Fault Tolerance 44
2.6 Timing Model 46
2.7 Summary 52
3 Modelling Fault Assumptions with Structural Failure Models 54
3.1 Related Work 55
3.2 Functional Failure Models 57
3.3 Structural Failure Models 62
3.4 Component Failure Models 65
3.4.1 Process Failure Models 66
3.4.2 Channel Failure Models 70
3.4.3 Hybrid Failure Models 73
3.5 Set-Based Structural Failure Models 75
3.5.1 Dependent Faults 76
3.5.2 Set-Based Structural Failure Models 78
3.5.3 Threshold Assumptions and Dependent Faults 87
3.5.4 Classes of Set-Based Structural Failure Models 89
3.6 Sequence-Based Structural Failure Models 104
3.7 Stochastics, Sets, and Sequences 107
3.8 Summary 109
4 Constructing Coteries 111
4.1 Related Work 113
4.2 Introduction to Quorums 115
4.3 Highly Available Static Coteries 123
4.4 Highly Available Dynamic Coteries 132
4.5 Reducing Probe Complexity 140
4.6 Summary 151
5 Reaching Consensus 153
5.1 Related Work 155
5.2 Introduction to Consensus 157
5.2.1 Specifying Consensus 157
5.2.2 The FLP Impossibility Result 161
5.2.3 Principles of Solving Consensus 162
5.2.4 Quality of Consensus Algorithms 164
5.3 Consensus in Asynchronous Systems with Unreliable Failure Detectors 168
5.3.1 A Versatile Consensus Algorithm 169
5.3.2 Adversary Structures 173
5.3.3 Didep Models 176
5.4 Consensus in Partially Synchronous Systems 183
5.5 Consensus in Synchronous Systems 188
5.6 Summary 200
6 Conclusion and Future Work 202
Bibliography 207
Index 224

Produkt-Details

• Erscheint lt. Verlag: 28.1.2011
• Reihe/Serie: Software Engineering Research
• Reihe/Serie: Software Engineering Research
• Zusatzinfo: XV, 216 p. 23 illus.
• Verlagsort: Wiesbaden
• Sprache: englisch
• Themenwelt: Mathematik / Informatik ► Informatik ► Netzwerke
• Themenwelt: Mathematik / Informatik ► Informatik ► Software Entwicklung
• Schlagworte: computing • Dependability • Design • failure models • fault tolerance • Modeling • Structural Failure Models
• ISBN-10: 3-8348-9707-8 / 3834897078
• ISBN-13: 978-3-8348-9707-7 / 9783834897077