List of Figures ................................................ XI
List of Symbols .............................................. XIII
Foreword by Michel Raynal ...................................... XV
Authors' Preface .............................................. XIX
1 Introduction ................................................. 1
1.1 Do-All Computing ........................................ 2
1.2 Do-All and Adversity .................................... 4
1.3 Solving Do-All: Fault-Tolerance with Efficiency ......... 6
1.4 Chapter Notes ........................................... 8
2 Distributed Cooperation Problems: Models and Definitions .... 11
2.1 Model of Computation ................................... 11
2.1.1 Distributed Setting ............................. 11
2.1.2 Communication ................................... 11
2.2 Models of Adversity .................................... 12
2.2.1 Processor Failure Types ......................... 12
2.2.2 Network Partitions .............................. 13
2.2.3 Adversaries and their Behavior .................. 13
2.3 Tasks and Do-All Computing ............................. 14
2.3.1 The Do-All Problem .............................. 15
2.3.2 The Omni-Do Problem ............................. 16
2.4 Measures of Efficiency ................................. 17
2.5 Chapter Notes .......................................... 19
3 Synchronous Do-All with Crashes: Using Perfect Knowledge
and Reliable Multicast ...................................... 21
3.1 Adversarial Model ...................................... 22
3.2 Lower and Upper Bounds for Abstract Models ............. 22
3.2.1 Modeling Knowledge .............................. 22
3.2.2 Lower Bounds .................................... 23
3.2.3 Upper Bounds .................................... 28
3.3 Solving Do-All Using Reliable Multicast ................ 33
3.3.1 Algorithm AN .................................... 34
3.3.2 Correctness of algorithm AN ..................... 38
3.3.3 Analysis of Algorithm AN ........................ 40
3.3.4 Analysis of Message-Passing Iterative Do-All .... 44
3.4 Open Problems .......................................... 45
3.5 Chapter Notes .......................................... 45
4 Synchronous Do-All with Crashes and Point-to-Point
Messaging ................................................... 47
4.1 The Gossip Problem ..................................... 48
4.2 Combinatorial Tools .................................... 49
4.2.1 Communication Graphs ............................ 49
4.2.2 Sets of Permutations ............................ 50
4.3 The Gossip Algorithm ................................... 51
4.3.1 Description of Algorithm Gossipε ................ 51
4.3.2 Correctness of Algorithm GossiPε ................ 55
4.3.3 Analysis of Algorithm GossiPe ................... 59
4.4 The Do-All Algorithm ................................... 61
4.4.1 Description of Algorithm Doallε ................. 62
4.4.2 Correctness of Algorithm Doallε ................. 64
4.4.3 Analysis of Algorithm Doallε .................... 67
4.5 Open Problems .......................................... 72
4.6 Chapter Notes .......................................... 73
5 Synchronous Do-All with Crashes and Restarts ................ 77
5.1 Adversarial Model ...................................... 78
5.2 A Lower Bound on Work for Restartable Processors ....... 79
5.3 Algorithm AR for Restartable Processors ................ 82
5.3.1 Description of Algorithm AR ..................... 82
5.3.2 Correctness of Algorithm AR ..................... 86
5.3.3 Complexity Analysis of Algorithm AR ............. 89
5.4 Open Problems .......................................... 92
5.5 Chapter Notes .......................................... 93
6 Synchronous Do-All with Byzantine Failures .................. 95
6.1 Adversarial Model ...................................... 96
6.2 Task Execution without Verification .................... 96
6.2.1 Known Maximum Number of Failures ................ 96
6.2.2 Unknown Maximum Number of Failures .............. 98
6.3 Task Execution with Verification ....................... 98
6.3.1 Known Maximum Number of Failures ................ 99
6.3.2 Unknown Maximum Number of Failures ............. 111
6.4 Open Problems ......................................... 112
6.5 Chapter Notes ......................................... 112
7 Asynchrony and Delay-Sensitive Bounds ...................... 115
7.1 Adversarial Model and Complexity ...................... 116
7.2 Delay-Sensitive Lower Bounds on Work .................. 118
7.2.1 Deterministic Delay-Sensitive Lower Bound ...... 119
7.2.2 Delay-sensitive Lower Bound for Randomized
Algorithms ..................................... 121
7.3 Contention of Permutations ............................ 125
7.3.1 Contention and Oblivious Tasks Scheduling ...... 127
7.3.2 Generalized Contention ......................... 128
7.4 Deterministic Algorithms Family DA .................... 130
7.4.1 Construction and Correctness of Algorithm
DA(q) .......................................... 131
7.4.2 Complexity Analysis of Algorithm DA(q) ......... 134
7.5 Permutation Algorithms Family PA ...................... 137
7.5.1 Algorithm Specification ........................ 137
7.5.2 Complexity Analysis ............................ 139
7.6 Open Problems ......................................... 142
7.7 Chapter Notes ......................................... 143
8 Analysis of Omni-Do in Asynchronous Partitionable
Networks ................................................... 145
8.1 Models of Adversity ................................... 146
8.2 A Group Communication Service and Notation ............ 148
8.3 View-Graphs ........................................... 150
8.4 Algorithm AX .......................................... 154
8.4.1 Description of the Algorithm ................... 154
8.4.2 Correctness of the Algorithm ................... 155
8.5 Analysis of Algorithm AX .............................. 158
8.5.1 Work Complexity ................................ 158
8.5.2 Message Complexity ............................. 162
8.5.3 Analysis Under Adversary AF .................... 165
8.6 Open Problems ......................................... 165
8.7 Chapter Notes ......................................... 166
9 Competitive Analysis of Omni-Do in Partitionable Networks .. 169
9.1 Model of Adversity, Competitiveness and Definitions ... 170
9.1.1 Adversary AGR .................................. 171
9.1.2 Measuring Competitiveness ...................... 173
9.1.3 Formalizing Computation Width .................. 174
9.2 Algorithm RS and its Analysis ......................... 175
9.2.1 Description of Algorithm RS .................... 175
9.2.2 Analysis of Algorithm RS ....................... 175
9.2.3 Deterministic Algorithms ....................... 178
9.3 Lower Bounds .......................................... 179
9.4 Open Problems ......................................... 181
9.5 Chapter Notes ......................................... 181
10 Cooperation in the Absence of Communication ................ 183
10.1 Adversity, Schedules, Waste, and Designs .............. 184
10.2 Redundancy without Communication: a Lower Bound ....... 187
10.3 Random Schedules ...................................... 188
10.4 Derandomization via Finite Geometries ................. 190
10.5 Open Problems ......................................... 192
10.6 Chapter Notes ......................................... 192
11 Related Cooperation Problems and Models .................... 195
11.1 Do-All in Shared-Memory ............................... 195
11.2 Do-All with Broadcast Channels ........................ 200
11.3 Consensus and its Connection to Do-Аll ................ 202
References ................................................. 205
Index ......................................................... 213
|
