Available:*
Library | Item Barcode | Call Number | Material Type | Item Category 1 | Status |
---|---|---|---|---|---|
Searching... | 30000010167786 | QA76.9.D5 G83 2006 | Open Access Book | Book | Searching... |
On Order
Summary
Summary
In modern computing a program is usually distributed among several processes. The fundamental challenge when developing reliable distributed programs is to support the cooperation of processes required to execute a common task, even when some of these processes fail. Guerraoui and Rodrigues present an introductory description of fundamental reliable distributed programming abstractions as well as algorithms to implement these abstractions. The authors follow an incremental approach by first introducing basic abstractions in simple distributed environments, before moving to more sophisticated abstractions and more challenging environments. Each core chapter is devoted to one specific class of abstractions, covering reliable delivery, shared memory, consensus and various forms of agreement. This textbook comes with a companion set of running examples implemented in Java. These can be used by students to get a better understanding of how reliable distributed programming abstractions can be implemented and used in practice. Combined, the chapters deliver a full course on reliable distributed programming. The book can also be used as a complete reference on the basic elements required to build reliable distributed applications.
Table of Contents
1 Introduction | p. 1 |
1.1 Motivation | p. 1 |
1.2 Distributed Programming Abstractions | p. 3 |
1.2.1 Inherent Distribution | p. 4 |
1.2.2 Distribution as an Artifact | p. 6 |
1.3 The End-to-End Argument | p. 7 |
1.4 Software Components | p. 8 |
1.4.1 Composition Model | p. 8 |
1.4.2 Programming Interface | p. 10 |
1.4.3 Modules | p. 11 |
1.4.4 Classes of Algorithms | p. 13 |
1.5 Hands-On | p. 15 |
1.5.1 Print Module | p. 16 |
1.5.2 BoundedPrint Module | p. 18 |
1.5.3 Composing Modules | p. 20 |
2 Basic Abstractions | p. 25 |
2.1 Distributed Computation | p. 26 |
2.1.1 Processes and Messages | p. 26 |
2.1.2 Automata and Steps | p. 26 |
2.1.3 Liveness and Safety | p. 28 |
2.2 Abstracting Processes | p. 29 |
2.2.1 Process Failures | p. 29 |
2.2.2 Arbitrary Faults and Omissions | p. 30 |
2.2.3 Crashes | p. 30 |
2.2.4 Recoveries | p. 32 |
2.3 Abstracting Communication | p. 34 |
2.3.1 Link Failures | p. 35 |
2.3.2 Fair-Loss Links | p. 36 |
2.3.3 Stubborn Links | p. 36 |
2.3.4 Perfect Links | p. 38 |
2.3.5 Logged Perfect Links | p. 40 |
2.3.6 On the Link Abstractions | p. 41 |
2.4 Timing Assumptions | p. 43 |
2.4.1 Asynchronous System | p. 43 |
2.4.2 Synchronous System | p. 45 |
2.4.3 Partial Synchrony | p. 46 |
2.5 Abstracting Time | p. 47 |
2.5.1 Failure Detection | p. 47 |
2.5.2 Perfect Failure Detection | p. 48 |
2.5.3 Leader Election | p. 50 |
2.5.4 Eventually Perfect Failure Detection | p. 51 |
2.5.5 Eventual Leader Election | p. 54 |
2.6 Distributed System Models | p. 58 |
2.6.1 Combining Abstractions | p. 58 |
2.6.2 Measuring Performance | p. 59 |
2.7 Hands-On | p. 60 |
2.7.1 Sendable Event | p. 60 |
2.7.2 Message and Extended Message | p. 61 |
2.7.3 Fair-Loss Point-to-Point Links | p. 62 |
2.7.4 Perfect Point-to-Point Links | p. 62 |
2.7.5 Perfect Failure Detector | p. 63 |
2.8 Exercises | p. 64 |
2.9 Solutions | p. 65 |
2.10 Historical Notes | p. 67 |
3 Reliable Broadcast | p. 69 |
3.1 Motivation | p. 69 |
3.1.1 Client-Server Computing | p. 69 |
3.1.2 Multi-participant Systems | p. 70 |
3.2 Best-Effort Broadcast | p. 71 |
3.2.1 Specification | p. 71 |
3.2.2 Fail-Silent Algorithm: Basic Broadcast | p. 71 |
3.3 Regular Reliable Broadcast | p. 72 |
3.3.1 Specification | p. 73 |
3.3.2 Fail-Stop Algorithm: Lazy Reliable Broadcast | p. 73 |
3.3.3 Fail-Silent Algorithm: Eager Reliable Broadcast | p. 74 |
3.4 Uniform Reliable Broadcast | p. 76 |
3.4.1 Specification | p. 77 |
3.4.2 Fail-Stop Algorithm: All-Ack Uniform Reliable Broadcast | p. 78 |
3.4.3 Fail-Silent Algorithm: Majority-Ack Uniform Reliable Broadcast | p. 79 |
3.5 Stubborn Broadcast | p. 81 |
3.5.1 Overview | p. 81 |
3.5.2 Specification | p. 81 |
3.5.3 Fail-Recovery Algorithm: Basic Stubborn Broadcast | p. 82 |
3.6 Logged Best-Effort Broadcast | p. 83 |
3.6.1 Specification | p. 83 |
3.6.2 Fail-Recovery Algorithm: Logged Basic Broadcast | p. 83 |
3.7 Logged Uniform Reliable Broadcast | p. 84 |
3.7.1 Specification | p. 85 |
3.7.2 Fail-Recovery Algorithm: Logged Majority-Ack URB | p. 86 |
3.8 Randomized Broadcast | p. 86 |
3.8.1 The Scalability of Reliable Broadcast | p. 87 |
3.8.2 Epidemic Dissemination | p. 88 |
3.8.3 Specification | p. 88 |
3.8.4 Randomized Algorithm: Eager Probabilistic Broadcast | p. 89 |
3.8.5 Randomized Algorithm: Lazy Probabilistic Broadcast | p. 91 |
3.9 Causal Broadcast | p. 94 |
3.9.1 Overview | p. 94 |
3.9.2 Specifications | p. 94 |
3.9.3 Fail-Silent Algorithm: No-Waiting Causal Broadcast | p. 96 |
3.9.4 Fail-Stop Extension: Garbage Collecting the Causal Past | p. 98 |
3.9.5 Fail-Silent Algorithm: Waiting Causal Broadcast | p. 98 |
3.10 Hands-On | p. 101 |
3.10.1 Basic Broadcast | p. 101 |
3.10.2 Lazy Reliable Broadcast | p. 103 |
3.10.3 All-Ack Uniform Reliable Broadcast | p. 106 |
3.10.4 Majority-Ack URB | p. 108 |
3.10.5 Probabilistic Reliable Broadcast | p. 109 |
3.10.6 No-Waiting Causal Broadcast | p. 112 |
3.10.7 No-Waiting Causal Broadcast with Garbage Collection | p. 116 |
3.10.8 Waiting Causal Broadcast | p. 122 |
3.11 Exercises | p. 125 |
3.12 Solutions | p. 127 |
3.13 Historical Notes | p. 133 |
4 Shared Memory | p. 135 |
4.1 Introduction | p. 135 |
4.1.1 Sharing Information in a Distributed System | p. 135 |
4.1.2 Register Overview | p. 136 |
4.1.3 Completeness and Precedence | p. 139 |
4.2 (1, N) Regular Register | p. 140 |
4.2.1 Specification | p. 140 |
4.2.2 Fail-Stop Algorithm: Read-One Write-All Regular Register | p. 140 |
4.2.3 Fail-Silent Algorithm: Majority Voting Regular Register | p. 143 |
4.3 (1, N) Atomic Register | p. 146 |
4.3.1 Specification | p. 146 |
4.3.2 Transformation: From (1, N) Regular to (1, N) Atomic | p. 149 |
4.3.3 Fail-Stop Algorithm: Read-Impose Write-All (1, N) Atomic Register | p. 153 |
4.3.4 Fail-Silent Algorithm: Read-Impose Write-Majority (1, N) Atomic Register | p. 155 |
4.4 (N, N) Atomic Register | p. 157 |
4.4.1 Multiple Writers | p. 157 |
4.4.2 Specification | p. 158 |
4.4.3 Transformation: From (1, N) Atomic to (N, N) Atomic Registers | p. 159 |
4.4.4 Fail-Stop Algorithm: Read-Impose Write-Consult (N, N) Atomic Register | p. 162 |
4.4.5 Fail-Silent Algorithm: Read-Impose Write-Consult-Majority (N, N) Atomic Register | p. 162 |
4.5 (1, N) Logged Regular Register | p. 164 |
4.5.1 Precedence in the Fail-Recovery Model | p. 165 |
4.5.2 Specification | p. 166 |
4.5.3 Fail-Recovery Algorithm: Logged-Majority-Voting | p. 167 |
4.6 Hands-On | p. 171 |
4.6.1 (1, N) Regular Register | p. 171 |
4.6.2 (1, N) Atomic Register | p. 174 |
4.6.3 (N, N) Atomic Register | p. 178 |
4.7 Exercises | p. 181 |
4.8 Solutions | p. 182 |
4.9 Historical Notes | p. 187 |
5 Consensus | p. 189 |
5.1 Regular Consensus | p. 189 |
5.1.1 Specification | p. 189 |
5.1.2 Fail-Stop Algorithm: Flooding Consensus | p. 190 |
5.1.3 Fail-Stop Algorithm: Hierarchical Consensus | p. 193 |
5.2 Uniform Consensus | p. 195 |
5.2.1 Specification | p. 195 |
5.2.2 Fail-Stop Algorithm: Flooding Uniform Consensus | p. 196 |
5.2.3 Fail-Stop Algorithm: Hierarchical Uniform Consensus | p. 197 |
5.3 Abortable Consensus | p. 199 |
5.3.1 Overview | p. 199 |
5.3.2 Specification | p. 200 |
5.3.3 Fail-Silent Algorithm: RW Abortable Consensus | p. 201 |
5.3.4 Fail-Noisy Algorithm: From Abortable Consensus to Consensus | p. 204 |
5.4 Logged Abortable Consensus and Logged Consensus | p. 206 |
5.4.1 Fail-Recovery Algorithm: Logged Abortable Consensus | p. 206 |
5.5 Randomized Consensus | p. 208 |
5.5.1 Specification | p. 208 |
5.5.2 Randomized Algorithm: Probabilistic Consensus | p. 209 |
5.6 Hands-On | p. 212 |
5.6.1 Flooding Regular Consensus Protocol | p. 212 |
5.6.2 Hierarchical Regular Consensus Protocol | p. 216 |
5.6.3 Flooding Uniform Consensus | p. 219 |
5.6.4 Hierarchical Uniform Consensus | p. 222 |
5.7 Exercises | p. 225 |
5.8 Solutions | p. 226 |
5.9 Historical Notes | p. 232 |
6 Consensus Variants | p. 233 |
6.1 Total Order Broadcast | p. 233 |
6.1.1 Overview | p. 233 |
6.1.2 Specifications | p. 234 |
6.1.3 Algorithm: Consensus-Based Total Order Broadcast | p. 236 |
6.2 Terminating Reliable Broadcast | p. 239 |
6.2.1 Overview | p. 239 |
6.2.2 Specification | p. 240 |
6.2.3 Algorithm: Consensus-Based TRB | p. 240 |
6.3 Non-blocking Atomic Commit | p. 242 |
6.3.1 Overview | p. 242 |
6.3.2 Specification | p. 243 |
6.3.3 Algorithm: Consensus-Based NBAC | p. 244 |
6.4 Group Membership | p. 246 |
6.4.1 Overview | p. 246 |
6.4.2 Specification | p. 247 |
6.4.3 Algorithm: Consensus-Based Group Membership | p. 248 |
6.5 View Synchronous Communication | p. 249 |
6.5.1 Overview | p. 249 |
6.5.2 Specification | p. 250 |
6.5.3 Algorithm: TRB-Based View Synchronous Broadcast | p. 251 |
6.5.4 Algorithm: Consensus-Based Uniform View Synchronous Broadcast | p. 255 |
6.6 Hands-On | p. 258 |
6.6.1 Uniform Total Order Broadcast | p. 258 |
6.6.2 Consensus-Based Non-blocking Atomic Commit | p. 263 |
6.6.3 Consensus-Based Group Membership | p. 266 |
6.6.4 TRB-Based View Synchrony | p. 269 |
6.7 Exercices | p. 275 |
6.8 Solutions | p. 276 |
6.9 Historical Notes | p. 285 |
7 Concluding Remarks | p. 287 |
7.1 Further Implementations | p. 287 |
7.2 Further Readings | p. 289 |
Bibliography | p. 296 |
Index | p. 297 |