Cover image for Introduction to reliable distributed programming
Title:
Introduction to reliable distributed programming
Personal Author:
Publication Information:
Berlin : Springer, 2006
ISBN:
9783540288459
Added Author:

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 Introductionp. 1
1.1 Motivationp. 1
1.2 Distributed Programming Abstractionsp. 3
1.2.1 Inherent Distributionp. 4
1.2.2 Distribution as an Artifactp. 6
1.3 The End-to-End Argumentp. 7
1.4 Software Componentsp. 8
1.4.1 Composition Modelp. 8
1.4.2 Programming Interfacep. 10
1.4.3 Modulesp. 11
1.4.4 Classes of Algorithmsp. 13
1.5 Hands-Onp. 15
1.5.1 Print Modulep. 16
1.5.2 BoundedPrint Modulep. 18
1.5.3 Composing Modulesp. 20
2 Basic Abstractionsp. 25
2.1 Distributed Computationp. 26
2.1.1 Processes and Messagesp. 26
2.1.2 Automata and Stepsp. 26
2.1.3 Liveness and Safetyp. 28
2.2 Abstracting Processesp. 29
2.2.1 Process Failuresp. 29
2.2.2 Arbitrary Faults and Omissionsp. 30
2.2.3 Crashesp. 30
2.2.4 Recoveriesp. 32
2.3 Abstracting Communicationp. 34
2.3.1 Link Failuresp. 35
2.3.2 Fair-Loss Linksp. 36
2.3.3 Stubborn Linksp. 36
2.3.4 Perfect Linksp. 38
2.3.5 Logged Perfect Linksp. 40
2.3.6 On the Link Abstractionsp. 41
2.4 Timing Assumptionsp. 43
2.4.1 Asynchronous Systemp. 43
2.4.2 Synchronous Systemp. 45
2.4.3 Partial Synchronyp. 46
2.5 Abstracting Timep. 47
2.5.1 Failure Detectionp. 47
2.5.2 Perfect Failure Detectionp. 48
2.5.3 Leader Electionp. 50
2.5.4 Eventually Perfect Failure Detectionp. 51
2.5.5 Eventual Leader Electionp. 54
2.6 Distributed System Modelsp. 58
2.6.1 Combining Abstractionsp. 58
2.6.2 Measuring Performancep. 59
2.7 Hands-Onp. 60
2.7.1 Sendable Eventp. 60
2.7.2 Message and Extended Messagep. 61
2.7.3 Fair-Loss Point-to-Point Linksp. 62
2.7.4 Perfect Point-to-Point Linksp. 62
2.7.5 Perfect Failure Detectorp. 63
2.8 Exercisesp. 64
2.9 Solutionsp. 65
2.10 Historical Notesp. 67
3 Reliable Broadcastp. 69
3.1 Motivationp. 69
3.1.1 Client-Server Computingp. 69
3.1.2 Multi-participant Systemsp. 70
3.2 Best-Effort Broadcastp. 71
3.2.1 Specificationp. 71
3.2.2 Fail-Silent Algorithm: Basic Broadcastp. 71
3.3 Regular Reliable Broadcastp. 72
3.3.1 Specificationp. 73
3.3.2 Fail-Stop Algorithm: Lazy Reliable Broadcastp. 73
3.3.3 Fail-Silent Algorithm: Eager Reliable Broadcastp. 74
3.4 Uniform Reliable Broadcastp. 76
3.4.1 Specificationp. 77
3.4.2 Fail-Stop Algorithm: All-Ack Uniform Reliable Broadcastp. 78
3.4.3 Fail-Silent Algorithm: Majority-Ack Uniform Reliable Broadcastp. 79
3.5 Stubborn Broadcastp. 81
3.5.1 Overviewp. 81
3.5.2 Specificationp. 81
3.5.3 Fail-Recovery Algorithm: Basic Stubborn Broadcastp. 82
3.6 Logged Best-Effort Broadcastp. 83
3.6.1 Specificationp. 83
3.6.2 Fail-Recovery Algorithm: Logged Basic Broadcastp. 83
3.7 Logged Uniform Reliable Broadcastp. 84
3.7.1 Specificationp. 85
3.7.2 Fail-Recovery Algorithm: Logged Majority-Ack URBp. 86
3.8 Randomized Broadcastp. 86
3.8.1 The Scalability of Reliable Broadcastp. 87
3.8.2 Epidemic Disseminationp. 88
3.8.3 Specificationp. 88
3.8.4 Randomized Algorithm: Eager Probabilistic Broadcastp. 89
3.8.5 Randomized Algorithm: Lazy Probabilistic Broadcastp. 91
3.9 Causal Broadcastp. 94
3.9.1 Overviewp. 94
3.9.2 Specificationsp. 94
3.9.3 Fail-Silent Algorithm: No-Waiting Causal Broadcastp. 96
3.9.4 Fail-Stop Extension: Garbage Collecting the Causal Pastp. 98
3.9.5 Fail-Silent Algorithm: Waiting Causal Broadcastp. 98
3.10 Hands-Onp. 101
3.10.1 Basic Broadcastp. 101
3.10.2 Lazy Reliable Broadcastp. 103
3.10.3 All-Ack Uniform Reliable Broadcastp. 106
3.10.4 Majority-Ack URBp. 108
3.10.5 Probabilistic Reliable Broadcastp. 109
3.10.6 No-Waiting Causal Broadcastp. 112
3.10.7 No-Waiting Causal Broadcast with Garbage Collectionp. 116
3.10.8 Waiting Causal Broadcastp. 122
3.11 Exercisesp. 125
3.12 Solutionsp. 127
3.13 Historical Notesp. 133
4 Shared Memoryp. 135
4.1 Introductionp. 135
4.1.1 Sharing Information in a Distributed Systemp. 135
4.1.2 Register Overviewp. 136
4.1.3 Completeness and Precedencep. 139
4.2 (1, N) Regular Registerp. 140
4.2.1 Specificationp. 140
4.2.2 Fail-Stop Algorithm: Read-One Write-All Regular Registerp. 140
4.2.3 Fail-Silent Algorithm: Majority Voting Regular Registerp. 143
4.3 (1, N) Atomic Registerp. 146
4.3.1 Specificationp. 146
4.3.2 Transformation: From (1, N) Regular to (1, N) Atomicp. 149
4.3.3 Fail-Stop Algorithm: Read-Impose Write-All (1, N) Atomic Registerp. 153
4.3.4 Fail-Silent Algorithm: Read-Impose Write-Majority (1, N) Atomic Registerp. 155
4.4 (N, N) Atomic Registerp. 157
4.4.1 Multiple Writersp. 157
4.4.2 Specificationp. 158
4.4.3 Transformation: From (1, N) Atomic to (N, N) Atomic Registersp. 159
4.4.4 Fail-Stop Algorithm: Read-Impose Write-Consult (N, N) Atomic Registerp. 162
4.4.5 Fail-Silent Algorithm: Read-Impose Write-Consult-Majority (N, N) Atomic Registerp. 162
4.5 (1, N) Logged Regular Registerp. 164
4.5.1 Precedence in the Fail-Recovery Modelp. 165
4.5.2 Specificationp. 166
4.5.3 Fail-Recovery Algorithm: Logged-Majority-Votingp. 167
4.6 Hands-Onp. 171
4.6.1 (1, N) Regular Registerp. 171
4.6.2 (1, N) Atomic Registerp. 174
4.6.3 (N, N) Atomic Registerp. 178
4.7 Exercisesp. 181
4.8 Solutionsp. 182
4.9 Historical Notesp. 187
5 Consensusp. 189
5.1 Regular Consensusp. 189
5.1.1 Specificationp. 189
5.1.2 Fail-Stop Algorithm: Flooding Consensusp. 190
5.1.3 Fail-Stop Algorithm: Hierarchical Consensusp. 193
5.2 Uniform Consensusp. 195
5.2.1 Specificationp. 195
5.2.2 Fail-Stop Algorithm: Flooding Uniform Consensusp. 196
5.2.3 Fail-Stop Algorithm: Hierarchical Uniform Consensusp. 197
5.3 Abortable Consensusp. 199
5.3.1 Overviewp. 199
5.3.2 Specificationp. 200
5.3.3 Fail-Silent Algorithm: RW Abortable Consensusp. 201
5.3.4 Fail-Noisy Algorithm: From Abortable Consensus to Consensusp. 204
5.4 Logged Abortable Consensus and Logged Consensusp. 206
5.4.1 Fail-Recovery Algorithm: Logged Abortable Consensusp. 206
5.5 Randomized Consensusp. 208
5.5.1 Specificationp. 208
5.5.2 Randomized Algorithm: Probabilistic Consensusp. 209
5.6 Hands-Onp. 212
5.6.1 Flooding Regular Consensus Protocolp. 212
5.6.2 Hierarchical Regular Consensus Protocolp. 216
5.6.3 Flooding Uniform Consensusp. 219
5.6.4 Hierarchical Uniform Consensusp. 222
5.7 Exercisesp. 225
5.8 Solutionsp. 226
5.9 Historical Notesp. 232
6 Consensus Variantsp. 233
6.1 Total Order Broadcastp. 233
6.1.1 Overviewp. 233
6.1.2 Specificationsp. 234
6.1.3 Algorithm: Consensus-Based Total Order Broadcastp. 236
6.2 Terminating Reliable Broadcastp. 239
6.2.1 Overviewp. 239
6.2.2 Specificationp. 240
6.2.3 Algorithm: Consensus-Based TRBp. 240
6.3 Non-blocking Atomic Commitp. 242
6.3.1 Overviewp. 242
6.3.2 Specificationp. 243
6.3.3 Algorithm: Consensus-Based NBACp. 244
6.4 Group Membershipp. 246
6.4.1 Overviewp. 246
6.4.2 Specificationp. 247
6.4.3 Algorithm: Consensus-Based Group Membershipp. 248
6.5 View Synchronous Communicationp. 249
6.5.1 Overviewp. 249
6.5.2 Specificationp. 250
6.5.3 Algorithm: TRB-Based View Synchronous Broadcastp. 251
6.5.4 Algorithm: Consensus-Based Uniform View Synchronous Broadcastp. 255
6.6 Hands-Onp. 258
6.6.1 Uniform Total Order Broadcastp. 258
6.6.2 Consensus-Based Non-blocking Atomic Commitp. 263
6.6.3 Consensus-Based Group Membershipp. 266
6.6.4 TRB-Based View Synchronyp. 269
6.7 Exercicesp. 275
6.8 Solutionsp. 276
6.9 Historical Notesp. 285
7 Concluding Remarksp. 287
7.1 Further Implementationsp. 287
7.2 Further Readingsp. 289
Bibliographyp. 296
Indexp. 297