Muutke küpsiste eelistusi

Impossibility Results for Distributed Computing [Pehme köide]

4.50/5 (4 hinnangut Goodreads-ist)
,
Teised raamatud teemal:
Impossibility Results for Distributed ComputingSuurem pilt
Teised raamatud teemal:
Püsilink: https://www.kriso.ee/db/9781627051705.html
To understand the power of distributed systems, it is necessary to understand their inherent limitations: what problems cannot be solved in particular systems, or without sufficient resources (such as time or space). This book presents key techniques for proving such impossibility results and applies them to a variety of different problems in a variety of different system models. Insights gained from these results are highlighted, aspects of a problem that make it difficult are isolated, features of an architecture that make it inadequate for solving certain problems efficiently are identified, and different system models are compared.Table of Contents: Acknowledgments / Introduction / Indistinguishability / Shifting and Scaling / Scenario Arguments / Information Theory Arguments / Covering Arguments / Valency Arguments / Combinatorial Arguments / Reductions and Simulations / Bibliography / Authors' Biographies
Acknowledgments xiii
1 Introduction
1(2)
1.1 Unsolvability Results and Lower Bounds
1(1)
1.2 Why Study Impossibility Results?
1(1)
1.3 Structure of the Book
2(1)
2 Indistinguishability
3(14)
2.1 A Time Tradeoff Between READ and WRITE in the Implementation of a Register
5(1)
2.2 A Space Lower Bound for First-Come First-Served Mutual Exclusion
6(1)
2.3 A Lower Bound on the Step Complexity of Approximate Agreement
7(2)
2.4 Chain Arguments for Consensus
9(4)
2.5 Causality Arguments
13(4)
3 Shifting and Scaling
17(10)
3.1 Shifting Arguments
17(2)
3.2 Time Lower Bounds for Implementing a Multi-Writer Register
19(3)
3.3 Clock Synchronization without Drift
22(3)
3.4 Scaling Arguments
25(1)
3.5 Clock Synchronization with Drift
25(2)
4 Scenario Arguments
27(6)
4.1 Impossibility of Consensus with Arbitrary Process Failures
27(2)
4.2 Clock Synchronization with Arbitrary Process Failures
29(4)
5 Information Theory Arguments
33(10)
5.1 Lower Bounds using Single-Writer Registers
33(2)
5.2 The Round Complexity of OR
35(1)
5.3 The Round Complexity of Approximate Agreement
36(2)
5.4 Lower Bounds using More Powerful Objects
38(2)
5.5 The Round Complexity of Collect
40(1)
5.6 A Step Complexity Tradeoff for Synchronous Snapshots
41(2)
6 Covering Arguments
43(22)
6.1 A Space Lower Bound for Mutual Exclusion
44(3)
6.2 The Space Complexity of Timestamps
47(5)
6.3 Space and Step Complexity Lower Bounds for the Implementation of a Counter using Swap Objects
52(3)
6.4 A Lower Bound on Step Complexity for Space-Optimal Implementations of a Multi-Writer Snapshot
55(7)
6.5 A Lower Bound on the Number of Stalls Incurred by a Counter Implemented using Arbitrary Read-Modify-Write Primitives
62(3)
7 Valency Arguments
65(32)
7.1 The Unsolvability of Consensus using m-assignment
66(2)
7.2 The Round Complexity of Consensus
68(1)
7.3 The Unsolvability of Consensus in Asynchronous Message Passing Systems
69(1)
7.4 The Space Complexity of Consensus
70(11)
7.4.1 Anonymous Processes
71(4)
7.4.2 The General Case
75(6)
7.5 A Lower Bound on Expected Work for Randomized Consensus
81(16)
7.5.1 Chain Arguments
84(1)
7.5.2 Nullvalent Executions
85(5)
7.5.3 Bivalent Executions
90(6)
7.5.4 Putting the Pieces Together
96(1)
8 Combinatorial Arguments
97(26)
8.1 Unsolvability of Set Consensus
97(6)
8.2 A Lower Bound on UPDATE Time for a Single-Writer Snapshot
103(5)
8.3 A Lower Bound on the Solo Step Complexity of Weak Test&Set using Turin's Theorem
108(2)
8.4 Anonymous Conflict Detectors
110(3)
8.5 Yao's Principle
113(2)
8.6 Expected Step Complexity of Randomized Implementations of a Max Register
115(8)
9 Reductions and Simulations
123(12)
9.1 Simulations with Different Numbers of Processes
125(2)
9.2 The BG Simulation
127(4)
9.3 Round-by-Round Simulations
131(2)
9.4 Uncomputability of Consensus Number
133(2)
Bibliography 135(6)
Authors' Biographies 141