(Downloads - 0)
For more info about our services contact : help@bestpfe.com
Table of contents
1 Introduction
1.1 Context of the Thesis
1.2 Thesis Contributions
I Context
2 Model
2.1 Distributed System
2.1.1 Characteristics
2.1.2 Advantages
2.2 Communication Graph
2.3 Models Used in this Thesis
2.3.1 Generic Model
2.3.2 State Model
2.3.3 Message Passing Model
2.4 Fault Taxonomy
2.4.1 Faults
2.4.2 Fault Patterns
3 Taxonomy of Daemons
3.1 Characterization of Daemons
3.1.1 Distribution
3.1.2 Fairness
3.1.3 Boundedness
3.1.4 Enabledness
3.2 Comparing Daemons
3.2.1 Comparing daemon classes
3.2.2 Preserving execution properties
3.2.3 The Case of the Synchronous Daemon
3.2.4 A map of classical daemons
3.3 Daemon Transformers
4 Fault Tolerance
4.1 Tolerating Transient Fault Patterns
4.1.1 Weakening Self-Stabilization
4.1.2 Enhancing Self-Stabilization
4.2 Tolerating Composite Fault Patterns
4.2.1 Fault-Tolerant Self-Stabilization
4.2.2 Byzantine Tolerant Self-Stabilization
4.2.3 Strict Stabilization
4.3 Summary
II Atomic Register
5 Introduction of Part II
5.1 Problem and Related Works
5.1.1 Problem
5.1.2 Related Works
5.1.3 Specification
5.2 Contributions of Part II
6 Preliminaries
6.1 Data-Link Protocol
6.1.1 Problem and Related Works
6.1.2 Specification
6.1.3 Lower Bounds
6.1.4 Optimal Solution
6.1.5 Correctness Proof
6.2 Bounded Labelling Systems
6.2.1 Problem and Related Works
6.2.2 Solution
7 Atomic Register Simulation
7.1 The ABD Simulation
7.2 The FTPS Simulation
7.2.1 Distributed Protocol
7.2.2 Proof of Correctness
7.2.3 Conclusion
8 Conclusion of Part II
8.1 Summary of Contributions
8.2 Concluding Remarks
III Unison
9 Introduction of Part III
9.1 Problem and Related Works
9.1.1 Problem
9.1.2 Related Works
9.1.3 Specification and Definitions
9.2 Contributions of Part III
9.3 Fault-Tolerant Self-Stabilization
10 Impossibility Results
10.1 General Results
10.1.1 Two and more Byzantine Faults
10.1.2 Unfair Daemon
10.2 Minimal Unison Related Results
10.2.1 Weakly Fair Daemon
10.2.2 Strongly Fair Daemon and Maximal Degree greater than 3
10.3 Priority Unison Related Results
10.3.1 Weakly Fair Daemon
10.3.2 Strongly Fair Daemon and Maximal Degree greater than 3
10.4 Summary of Impossibility Results
11 Strictly Stabilizing Solution
11.1 Strictly Stabilizing Solution
11.1.1 Distributed Protocol Description
11.1.2 Correctness Proof
11.2 Optimality of Convergence Time
11.2.1 Upper bound
11.2.2 Lower Bound
11.2.3 Conclusion
12 Conclusion of Part III
12.1 Summary of Contributions
12.2 Concluding Remarks
IV Spanning Tree
13 Introduction of Part IV
13.1 Problem and Related Works
13.1.1 Related Works
13.1.2 Specification
13.2 Contributions of Part IV
13.3 Containing Byzantine Faults in Self-Stabilization
13.3.1 Strict Stabilization
13.3.2 Strong Stabilization
13.3.3 Topology-Aware Stabilization
13.3.4 Discussion
14 Two Case Studies
14.1 Spanning Tree without Constraints
14.1.1 Strongly Stabilizing Distributed Protocol
14.1.2 Proof of Strong Stabilization
14.2 BFS Spanning Tree
14.2.1 Impossibility of Strong Stabilization
14.2.2 Topology-Aware Stabilizing Solution
14.2.3 Proof of Topology-Aware Strict Stabilization
14.2.4 Proof of Topology-Aware Strong Stabilization
14.3 Summary
15 General Case
15.1 Topology-Aware Stabilizing Solution
15.1.1 Distributed Protocol
15.1.2 Proof of Topology-Aware Strict Stabilization
15.1.3 Proof of Topology-Aware Strong Stabilization
15.2 Optimality of Containment Areas
15.2.1 Topology-Aware Strict Stabilization
15.2.2 Topology-Aware Strong Stabilization
15.3 Strong Stabilization
15.4 Summary
16 Conclusion of Part IV
16.1 Summary of Contributions
16.2 Concluding Remarks
17 Conclusion
17.1 Overview of Thesis Contributions
17.1.1 Part One: Context
17.1.2 Part Two: Atomic Register
17.1.3 Part Three: Unison
17.1.4 Part Four: Spanning Tree
17.1.5 Summary
17.2 Perspectives
A Version française
A.1 Contexte de la thèse
A.1.1 Généralités
A.1.2 Modèles et tolérance aux fautes
A.2 Registre atomique
A.2.1 Contexte
A.2.2 Contributions
A.2.3 Perspectives
A.3 Unisson
A.3.1 Contexte
A.3.2 Contributions
A.3.3 Perspectives
A.4 Arbre couvrant
A.4.1 Contexte
A.4.2 Contributions
A.4.3 Perspectives
A.5 Conclusion
List of Notations
Bibliography
