(Downloads - 0)
For more info about our services contact : help@bestpfe.com
Table of contents
1 Introduction
1.1 Introduction française
1.2 Organization and Publications
2 General Notation
I Probabilistic Analysis of Distributed Dynamic Processes
3 Contributions Dynamic Processes
4 Social Networks: The Forest Fire Model [KLL+16]
4.1 Results
4.2 Approach and Technical Contributions
4.3 Related work
4.4 Relating graph and line process
4.4.1 Line process
4.4.2 The ambassador graph
4.4.3 Coupling
4.4.4 Proofs of the Graph results from the Line results – Proof of Theorem
4.1 and Theorem 4.3
4.5 Analysis of the Line Fire Process
4.5.1 High-Level Proof Overview
4.5.2 Proof of Lemma 4.4
4.5.3 Proof of Lemma 4.13
4.5.4 Proof of Proposition 4.14
4.5.5 The foundations of
4.6 Lower bound – Proof of Lemma 4.5
4.7 Future Work and Conclusion
4.7.1 Further models
4.7.2 Conclusion
5 Balls-into-Bins with Deleting Bins [BFK+16a]
5.1 Results
5.2 Approach and Technical Contributions
5.3 Related Work
5.4 Model & Preliminaries
5.5 The 1-Choice Process
5.5.1 Maximum Load – Proof of Theorem 5.2
5.5.2 Stability – Proof of Theorem 5.1
5.5.3 Lower Bound on Maximum Load – Proof of Theorem 5.3
5.6 The 2-Choice Process
5.6.1 Bounding the Smoothness – Proof of Proposition 5.7
5.6.2 Maximum Load – Proof of Theorem 5.6
5.6.3 Stability – Proof of Theorem 5.5
6 Future Work – Dynamic Processes
II Probabilistic Analysis of Consensus Dynamics and Protocols
7 Contributions Consensus Processes
7.1 Consensus Dynamics
7.1.1 Overview of Results
7.2 Consensus Protocols
7.2.1 Overview of Results
7.3 Related Work
7.3.1 Voter Model
7.3.2 2-Choices
7.3.3 3-Majority
7.3.4 Further Consensus Dynamics
7.3.5 Consensus Protocols
8 Voter Model [KMS16] 98
8.1 Results
8.2 Approach and Technical Contributions
8.3 Bounding the coalescence time
8.3.1 The coalescence process
8.3.2 A more amenable process
8.3.3 Meeting Time Distribution Prior to tmeet
8.3.4 Upper Bound – Proof of Theorem 8.1
8.3.5 Lower Bound – Proof of Theorem 8.2
9 3-Majority [BCE+17] 131
9.1 Results
9.2 Approach and Technical Contributions
9.3 Consensus Model & Technical Framework
9.3.1 Comparing Anonymous Consensus Processes
9.3.2 Coupling two AC-Processes – Proof of Theorem 9.4
9.4 Upper Bound for 3-Majority- Proof of Theorem 9.8
9.4.1 Analysis of Phase 1: 3-Majority vs. Voter
9.4.2 Analysis of Phase 1: A Bound for Voter
9.5 Limitations of 1-Step Coupling
10 2-Choices [EFK+16, BCE+17]
10.1 Results
10.2 Approach and Technical Contributions
10.3 Plurality Consensus with Two Choices
10.3.1 Upper bound – Proof of Theorem 10.2
10.4 Lower Bound for 2-Choices
10.4.1 Worst-Case Lower bound – Theorem 10.5
10.4.2 Complementing our Upper bounds Theorem 10.6 and Theorem 10.7
10.5 Comparison with the 3-Majority Process
11 Rapid Asynchronous Consensus [EFK+16]
11.1 Results
11.2 Approach and Technical Contributions
11.3 The Asynchronous Protocol
11.4 The Key Lemmas
11.5 Concentration of the Clocks: Proof of Proposition 11.3
11.6 Analysis of the 2-Choices sub-phase: Proof of Proposition 11.4
11.7 Analysis of the Bit-Propagation Sub-Phase: Proof of Proposition 11.5
11.8 The Endgame: Taking a from (1 − « Part1) · n to n
11.9 Putting Everything Together: Proof of Theorem 11.1
11.10Increasing the Number of Opinions
11.11Conclusions and Further Work
12 Consensus via Load Balancing [BFK+16b]
12.1 Results
12.2 Approach and Technical Contributions
12.3 Communication Model and Notation
12.4 Protocol Shuffle – Theorem 12.1
12.4.1 Protocol Description
12.4.2 Analysis of Shuffle
12.5 Protocol Balance – Theorem 12.9
13 Future Work – Distributed Consensus Processes
Bibliography
