Directed Dynamic Networks

For more info about our services contact : help@bestpfe.com

Table of contents

1 Introduction 
1.1 Contributions
1.1.1 A Failure Detector for k-Set Agreement in Unknown Dynamic Systems
1.1.2 A Failure Detector for Mutual Exclusion in Unknown Dynamic Systems .
1.1.3 An Asynchronous Reliable Broadcast Algorithm over a Hypercube Topology
1.2 Publications
1.2.1 Papers in International Conferences
1.2.2 Papers in International Journals
1.3 Organization of the Manuscript
2 A Background on Failure Detectors and Dynamic Systems 
2.1 Distributed Systems
2.1.1 Processes
2.1.2 Communication Models
2.1.3 Failure Models
2.1.4 Timing Models
2.1.5 Notations
2.2 Distributed Problems
2.2.1 Consensus and k-Set Agreement
2.2.2 Fault-Tolerant Mutual Exclusion
2.3 Failure Detectors
2.3.1 The Failure Detector Hierarchy
2.3.2 Failure Detectors for Consensus and k-Set Agreement in Message Passing Systems
2.3.3 Failure Detectors for Consensus and k-Set Agreement in Shared Memory Systems
2.3.4 Failure Detectors for Mutual Exclusion
2.4 Dynamic Networks
2.4.1 Increasing and Decreasing Systems with a Static Communication Graph .
2.4.2 The Dynamic Graph Model
2.4.3 Directed Dynamic Networks
2.4.4 Evolving Graphs
2.4.5 Time-Varying Graphs (TVG)
2.4.6 Unknown Asynchronous Dynamic Networks
2.4.7 Summary of Failure Detector Results in Unknown and/or Dynamic Systems
2.5 Conclusion
3 A Failure Detector for k-Set Agreement in Unknown Dynamic Systems 
3.1 System Model
3.1.1 Process Model
3.1.2 Communication Model
3.2 Failure Detectors for k-Set Agreement in Unknown Dynamic Systems
3.2.1 The ?;k Failure Detector
3.2.2 The Family of Failure Detectors ?;x;y
3.3 Assumptions
3.3.1 Time-Varying Graph Classes
3.3.2 Message Pattern Assumptions
3.3.3 Summary of Assumptions
3.3.4 Implementation of Message Pattern Assumptions
3.3.5 Comparable Assumptions in the Literature
3.4 Failure Detector Algorithms
3.4.1 An Algorithm for ?;k
3.4.2 An Algorithm for ?;x
3.4.3 An Algorithm for ?;x;y
3.5 A k-Set Agreement Algorithm
3.5.1 The Alphax Sub Protocol
3.5.2 Alphax Algorithm
3.5.3 k-Set Agreement Algorithm
3.6 Conclusion
4 The Weakest Failure Detector for Mutual Exclusion in Unknown Dynamic Systems 
4.1 Model and Problem Definition
4.1.1 System Model
4.1.2 Failure Model
4.1.3 Connectivity Model
4.1.4 Knowledge Model
4.1.5 Problem Definition
4.2 Failure Detectors for Mutual Exclusion in Unknown Dynamic Systems
4.2.1 The T l Failure Detector
4.2.2 The T lr Failure Detector
4.3 Sufficiency of T lr to solve Fault-Tolerant Mutual Exclusion
4.3.1 Algorithm Description
4.3.2 Proof of Correctness
4.4 Necessity of T lr to solve Fault-Tolerant Mutual Exclusion
5 Conclusion 
5.1 Contributions
5.1.1 A Failure Detector for k-Set Agreement in Unknown Dynamic Systems
5.1.2 A Failure Detector for Recoverable Mutual Exclusion in Unknown Dynamic Systems
5.2 Perspectives
5.2.1 On the Necessity of Synchronous Processes in Dynamic Systems
5.2.2 The Weakest Failure Detector for k-Set Agreement
5.2.3 Defining the Mutual Exclusion Problem in Crash-Recovery Systems
A A Reliable Broadcast Protocol for Asynchronous Systems with a Hypercube Topology 
A.1 Introduction
A.2 Related Work
A.3 System Model
A.4 The VCube
A.5 Reliable Broadcast Algorithm for Asynchronous System
A.5.1 Message types and local variables
A.5.2 Algorithm description
A.5.3 Proof of correctness
A.6 Performance Discussion
A.7 Conclusion and Future Work
Bibliography