Do-all computing in distributed systems : cooperation in the presence of adversity

Do-All Computing for Distributed Systems: Cooperation in the Presence of Adversity studies algorithmic issues associated with cooperative execution of multiple independent tasks by distributed computing agents including partitionable networks.

Recent results have shed light on the understanding of how adversity affects efficiency, by presenting failure-sensitive upper and lower bounds for Do-All in several models for computation. The ability to cooperatively perform a collection of tasks is key to solving a broad array of computation problems ranging from distributed search to distributed simulation and multi-agent collaboration which is introduced within this book.

Do-All Computing for Distributed Systems: Cooperation in the Presence of Adversity is structured to meet the needs of a professional audience composed of researchers and practitioners in industry. This volume is also suitable for graduate-level students in computer science.

Michel Raynal

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

Available:*

On Order

Summary

Summary

Table of Contents