Do-All Computing in Distributed Systems

by Georgiou, Chryssis; Shvartsman, Alex Allister

• ISBN13: 9780387309187
• ISBN10: 0387309187
• Format: Hardcover
• Copyright: 2007-11-01
• Publisher: Springer-Verlag New York Inc

Summary

The ability to cooperatively perform a collection of tasks in a distributed system is key to solving a broad array of computation problems ranging from distributed search to distributed simulation, and multi-agent collaboration. Practical solutions to such cooperation problems must effectively marshal the available computing resources in performing large sets of tasks. This is challenging due to the failures and asynchrony of the involved processors and due to the delays and connectivity failures in the underlying network.

Table of Contents

List of Figures	p. XI
List of Symbols	p. XIII
Foreword	p. XV
Authors' Preface	p. XIX
Introduction	p. 1
Do-All Computing	p. 2
Do-All and Adversity	p. 4
Solving Do-All: Fault-Tolerance with Efficiency	p. 6
Chapter Notes	p. 8
Distributed Cooperation Problems: Models and Definitions	p. 11
Model of Computation	p. 11
Distributed Setting	p. 11
Communication	p. 11
Models of Adversity	p. 12
Processor Failure Types	p. 12
Network Partitions	p. 13
Adversaries and their Behavior	p. 13
Tasks and Do-All Computing	p. 14
The Do-All Problem	p. 15
The Omni-Do Problem	p. 16
Measures of Efficiency	p. 17
Chapter Notes	p. 19
Synchronous Do-All with Crashes: Using Perfect Knowledge and Reliable Multicast	p. 21
Adversarial Model	p. 22
Lower and Upper Bounds for Abstract Models	p. 22
Modeling Knowledge	p. 22
Lower Bounds	p. 23
Upper Bounds	p. 28
Solving Do-All Using Reliable Multicast	p. 33
Algorithm AN	p. 34
Correctness of algorithm AN	p. 38
Analysis of Algorithm AN	p. 40
Analysis of Message-Passing Iterative Do-All	p. 44
Open Problems	p. 45
Chapter Notes	p. 45
Synchronous Do-All with Crashes and Point-to-Point Messaging	p. 47
The Gossip Problem	p. 48
Combinatorial Tools	p. 49
Communication Graphs	p. 49
Sets of Permutations	p. 50
The Gossip Algorithm	p. 51
Description of Algorithm Gossip[subscript epsilon]	p. 51
Correctness of Algorithm Gossip[subscript epsilon]	p. 55
Analysis of Algorithm Gossip[subscript epsilon]	p. 59
The Do-All Algorithm	p. 61
Description of Algorithm Doall[subscript epsilon]	p. 62
Correctness of Algorithm Doall[subscript epsilon]	p. 64
Analysis of Algorithm Doall[subscript epsilon]	p. 67
Open Problems	p. 72
Chapter Notes	p. 73
Synchronous Do-All with Crashes and Restarts	p. 77
Adversarial Model	p. 78
A Lower Bound on Work for Restartable Processors	p. 79
Algorithm AR for Restartable Processors	p. 82
Description of Algorithm AR	p. 82
Correctness of Algorithm AR	p. 86
Complexity Analysis of Algorithm AR	p. 89
Open Problems	p. 92
Chapter Notes	p. 93
Synchronous Do-All with Byzantine Failures	p. 95
Adversarial Model	p. 96
Task Execution without Verification	p. 96
Known Maximum Number of Failures	p. 96
Unknown Maximum Number of Failures	p. 98
Task Execution with Verification	p. 98
Known Maximum Number of Failures	p. 99
Unknown Maximum Number of Failures	p. 111
Open Problems	p. 112
Chapter Notes	p. 112
Asynchrony and Delay-Sensitive Bounds	p. 115
Adversarial Model and Complexity	p. 116
Delay-Sensitive Lower Bounds on Work	p. 118
Deterministic Delay-Sensitive Lower Bound	p. 119
Delay-sensitive Lower Bound for Randomized Algorithms	p. 121
Contention of Permutations	p. 125
Contention and Oblivious Tasks Scheduling	p. 127
Generalized Contention	p. 128
Deterministic Algorithms Family DA	p. 130
Construction and Correctness of Algorithm DA(q)	p. 131
Complexity Analysis of Algorithm DA(q)	p. 134
Permutation Algorithms Family PA	p. 137
Algorithm Specification	p. 137
Complexity Analysis	p. 139
Open Problems	p. 142
Chapter Notes	p. 143
Analysis of Omni-Do in Asynchronous Partitionable Networks	p. 145
Models of Adversity	p. 146
A Group Communication Service and Notation	p. 148
View-Graphs	p. 150
Algorithm AX	p. 154
Description of the Algorithm	p. 154
Correctness of the Algorithm	p. 155
Analysis of Algorithm AX	p. 158
Work Complexity	p. 158
Message Complexity	p. 162
Analysis Under Adversary A[subscript F]	p. 165
Open Problems	p. 165
Chapter Notes	p. 166
Competitive Analysis of Omni-Do in Partitionable Networks	p. 169
Model of Adversity, Competitiveness and Definitions	p. 170
Adversary A[subscript GR]	p. 171
Measuring Competitiveness	p. 173
Formalizing Computation Width	p. 174
Algorithm RS and its Analysis	p. 175
Description of Algorithm RS	p. 175
Analysis of Algorithm RS	p. 175
Deterministic Algorithms	p. 178
Lower Bounds	p. 179
Open Problems	p. 181
Chapter Notes	p. 181
Cooperation in the Absence of Communication	p. 183
Adversity, Schedules, Waste, and Designs	p. 184
Redundancy without Communication: a Lower Bound	p. 187
Random Schedules	p. 188
Derandomization via Finite Geometries	p. 190
Open Problems	p. 192
Chapter Notes	p. 192
Related Cooperation Problems and Models	p. 195
Do-All in Shared-Memory	p. 195
Do-All with Broadcast Channels	p. 200
Consensus and its Connection to Do-All	p. 202
References	p. 205
Index	p. 213
Table of Contents provided by Ingram. All Rights Reserved.