Distributed Systems: An Algorithmic Approach (Chapman & Hall/CRC Computer & Information Science Series)

c5645fm......Page 1
Distributed Systems: An Algorithmic Approach......Page 3
Preface......Page 5
Table of Contents......Page 7
Dedication......Page 16
Table of Contents......Page 0
Part A: Background Materials......Page 17
1.2 WHY DISTRIBUTED SYSTEMS?......Page 18
1.3 EXAMPLES OF DISTRIBUTED SYSTEMS......Page 19
1.4 IMPORTANT ISSUES IN DISTRIBUTED SYSTEMS......Page 21
1.5 COMMON SUBPROBLEMS......Page 23
1.6 IMPLEMENTING A DISTRIBUTED SYSTEM......Page 24
EXERCISES......Page 25
2.1.2 CLIENT–SERVER MODEL......Page 27
2.2 NETWORK PROTOCOLS......Page 28
2.2.2 WIRELESS NETWORKS......Page 29
2.2.3 THE OSI MODEL......Page 31
2.2.4 INTERNET PROTOCOL......Page 33
2.2.5 TRANSPORT LAYER PROTOCOLS......Page 34
2.2.6 INTERPROCESS COMMUNICATION USING SOCKETS......Page 35
2.3 NAMING......Page 36
2.3.1 DOMAIN NAME SERVICE......Page 37
2.3.2 NAMING SERVICE FOR MOBILE CLIENTS......Page 38
2.4.1 IMPLEMENTING RPC......Page 39
2.5 REMOTE METHOD INVOCATION......Page 41
2.6 WEB SERVICES......Page 42
2.8 EVENT NOTIFICATION......Page 43
2.9 CORBA......Page 44
2.10 MOBILE AGENTS......Page 45
2.13 BIBLIOGRAPHIC NOTES......Page 46
2.14 EXERCISES......Page 47
Part B: Foundational Topics......Page 48
3.2.1 PROCESS ACTIONS......Page 49
3.2.2 CHANNELS......Page 50
3.2.3 SYNCHRONOUS VS. ASYNCHRONOUS SYSTEMS......Page 51
3.3 SHARED VARIABLES......Page 53
3.3.1 LINDA......Page 54
3.4 MODELING MOBILE AGENTS......Page 55
3.5.1 STRONG AND WEAK MODELS......Page 56
3.5.2 IMPLEMENTING A FIFO CHANNEL USING A NON-FIFO CHANNEL......Page 57
3.5.4 IMPLEMENTING SHARED MEMORY USING MESSAGE PASSING......Page 58
3.5.5 AN IMPOSSIBILITY RESULT WITH CHANNELS......Page 59
3.7 COMPLEXITY MEASURES......Page 60
3.9 BIBLIOGRAPHIC NOTES......Page 63
EXERCISES......Page 64
4.2 GUARDED ACTIONS......Page 66
4.3 NONDETERMINISM......Page 68
4.4 ATOMIC OPERATIONS......Page 69
4.5 FAIRNESS......Page 71
4.5.2 WEAKLY FAIR SCHEDULER......Page 72
4.6 CENTRAL VS. DISTRIBUTED SCHEDULERS......Page 73
4.7 CONCLUDING REMARKS......Page 75
4.8 BIBLIOGRAPHIC NOTES......Page 76
EXERCISES......Page 77
5.1 INTRODUCTION......Page 80
5.2.1 SAFETY PROPERTIES......Page 81
5.2.2 LIVENESS PROPERTIES......Page 82
5.4.1 A REVIEW OF PROPOSITIONAL LOGIC......Page 85
5.4.2 BRIEF OVERVIEW OF PREDICATE LOGIC......Page 86
5.5 ASSERTIONAL REASONING: PROVING SAFETY PROPERTIES......Page 87
5.6 PROVING LIVENESS PROPERTIES USING WELL-FOUNDED SETS......Page 88
5.7 PROGRAMMING LOGIC......Page 90
5.8 PREDICATE TRANSFORMERS......Page 93
5.10 BIBLIOGRAPHIC NOTES......Page 95
EXERCISES......Page 96
6.1.1 THE PHYSICAL TIME......Page 99
6.2 LOGICAL CLOCKS......Page 100
6.3 VECTOR CLOCKS......Page 103
6.4.1 PRELIMINARY DEFINITIONS......Page 104
6.4.2 CLOCK READING ERROR......Page 105
6.4.3 ALGORITHMS INTERNAL SYNCHRONIZATION......Page 106
6.4.4 ALGORITHMS FOR EXTERNAL SYNCHRONIZATION......Page 107
6.5 CONCLUDING REMARKS......Page 109
EXERCISES......Page 110
Part C: Important Paradigms......Page 113
7.2 SOLUTIONS USING MESSAGE PASSING......Page 114
7.2.1 LAMPORT’S SOLUTION......Page 115
7.2.2 RICART–AGRAWALA’S SOLUTION......Page 117
7.2.3 MAEKAWA’S SOLUTION......Page 118
7.3.1 SUZUKI–KASAMI ALGORITHM......Page 122
7.4 SOLUTIONS ON THE SHARED-MEMORY MODEL......Page 123
7.4.1 PETERSON’S ALGORITHM......Page 124
7.5.1 SOLUTION USING TEST-AND-SET......Page 126
7.6 THE GROUP MUTUAL EXCLUSION PROBLEM......Page 127
7.6.2 DECENTRALIZED SOLUTION ON THE SHARED-MEMORY MODEL......Page 128
7.7 CONCLUDING REMARKS......Page 129
7.8 BIBLIOGRAPHIC NOTES......Page 130
EXERCISES......Page 131
8.1 INTRODUCTION......Page 135
8.2 PROPERTIES OF CONSISTENT SNAPSHOTS......Page 136
8.3 THE CHANDY–LAMPORT ALGORITHM......Page 137
8.3.1 TWO EXAMPLES......Page 139
8.4 THE LAI–YANG ALGORITHM......Page 141
EXERCISES......Page 142
9.2 AN ELEMENTARY ALGORITHM FOR BROADCASTING......Page 145
9.3 TERMINATION DETECTION ALGORITHM......Page 147
9.3.1 THE DIJKSTRA–SCHOLTEN ALGORITHM......Page 148
9.3.2 TERMINATION DETECTION ON A UNIDIRECTIONAL RING......Page 151
9.4 DISTRIBUTED DEADLOCK DETECTION......Page 152
9.4.1 DETECTION OF RESOURCE DEADLOCK......Page 153
9.4.2 DETECTION OF COMMUNICATION DEADLOCK......Page 155
9.5 CONCLUDING REMARKS......Page 156
EXERCISES......Page 157
10.2 ROUTING ALGORITHMS......Page 159
10.2.1 COMPUTATION OF SHORTEST PATH......Page 160
10.2.2 DISTANCE VECTOR ROUTING......Page 162
10.2.3 LINK-STATE ROUTING......Page 163
10.2.4 INTERVAL ROUTING......Page 164
10.3.1 SPANNING TREE CONSTRUCTION......Page 167
10.3.2 TARRY’S GRAPH TRAVERSAL ALGORITHM......Page 169
10.3.3 MINIMUM SPANNING TREE......Page 170
10.4 GRAPH COLORING......Page 174
10.4.1 A SIMPLE COLORING ALGORITHM......Page 175
10.4.2 PLANAR GRAPH COLORING......Page 176
10.5 CONCLUDING REMARKS......Page 177
EXERCISES......Page 178
11.2 LEADER ELECTION......Page 181
11.2.1 THE BULLY ALGORITHM......Page 182
11.2.2.1 Chang–Roberts Algorithm......Page 183
11.2.2.2 Franklin’s Algorithm......Page 184
11.2.2.3 Peterson’s Algorithm......Page 185
11.2.4 ELECTION IN ANONYMOUS NETWORKS......Page 187
11.3.1 THE ABD SYNCHRONIZER......Page 188
11.3.2.1 The alpha-Synchronizer......Page 189
11.3.2.3 The gamma-Synchronizer......Page 191
11.4 CONCLUDING REMARKS......Page 193
11.6 EXERCISES......Page 194
Part D: Faults and Fault-Tolerant Systems......Page 196
12.2 CLASSIFICATION OF FAULTS......Page 197
12.3 SPECIFICATION OF FAULTS......Page 200
12.4.3 FAIL-SAFE TOLERANCE......Page 202
12.4.5 DETECTION OF FAILURES......Page 203
12.5.1 TRIPLE MODULAR REDUNDANCY......Page 204
12.6 TOLERATING OMISSION FAILURES......Page 205
12.6.1 THE SLIDING WINDOW PROTOCOL......Page 206
12.6.2 THE ALTERNATING BIT PROTOCOL......Page 208
12.7 CONCLUDING REMARKS......Page 209
12.8 BIBLIOGRAPHIC NOTES......Page 210
12.9 EXERCISES......Page 211
13.1 INTRODUCTION......Page 214
13.2 CONSENSUS IN ASYNCHRONOUS SYSTEMS......Page 215
13.3 CONSENSUS ON SYNCHRONOUS SYSTEMS: BYZANTINE GENERALS PROBLEM......Page 218
13.3.3 CONSENSUS WITH ORAL MESSAGES......Page 219
13.3.3.1 An Impossibility Result......Page 220
13.3.3.2 The OM(m) Algorithm......Page 221
13.3.4 CONSENSUS USING SIGNED MESSAGES......Page 224
13.4 FAILURE DETECTORS......Page 225
13.4.1 SOLVING CONSENSUS USING FAILURE DETECTORS......Page 227
13.4.1.2 Consensus using S......Page 228
13.5 CONCLUDING REMARKS......Page 229
13.7 EXERCISES......Page 230
14.1 INTRODUCTION......Page 232
14.2 CLASSIFICATION OF TRANSACTIONS......Page 233
14.4 CONCURRENCY CONTROL AND SERIALIZABILITY......Page 234
14.4.1 TESTING FOR SERIALIZABILITY......Page 235
14.4.3 TIMESTAMP ORDERING......Page 236
14.5 ATOMIC COMMIT PROTOCOLS......Page 237
14.5.2 TWO-PHASE COMMIT......Page 238
14.5.3 NON-BLOCKING ATOMIC COMMIT......Page 239
14.6.1 STABLE STORAGE......Page 240
14.6.2 CHECKPOINTING AND ROLLBACK RECOVERY......Page 241
14.6.3 MESSAGE LOGGING......Page 242
14.7 CONCLUDING REMARKS......Page 243
14.9 EXERCISES......Page 244
15.2 ATOMIC MULTICAST......Page 247
15.3 IP MULTICAST......Page 248
15.4 APPLICATION LAYER MULTICAST......Page 250
15.5 ORDERED MULTICASTS......Page 251
15.5.1 IMPLEMENTING TOTAL ORDER MULTICAST......Page 252
15.5.2 IMPLEMENTING CAUSAL ORDER MULTICAST......Page 253
15.6.1 THE REQUIREMENTS OF RELIABLE MULTICAST......Page 254
15.6.2 SCALABLE RELIABLE MULTICAST......Page 255
15.7 OPEN GROUPS......Page 256
15.7.1 VIEW-SYNCHRONOUS GROUP COMMUNICATION......Page 257
15.8 AN OVERVIEW OF TRANSIS......Page 258
15.10 BIBLIOGRAPHIC NOTES......Page 259
15.11 EXERCISES......Page 260
APPENDIX. SIMULATION OF IMPERFECT CHANNELS......Page 262
16.1.1 RELIABILITY VS. AVAILABILITY......Page 267
16.2.1 PASSIVE VS. ACTIVE REPLICATION......Page 268
16.2.2 FAULT-TOLERANT STATE MACHINES......Page 270
16.3.1 STRICT CONSISTENCY......Page 271
16.3.2 LINEARIZABILITY......Page 272
16.3.3 SEQUENTIAL CONSISTENCY......Page 273
16.4 CLIENT-CENTRIC CONSISTENCY PROTOCOLS......Page 274
16.4.2 CONSISTENCY MODELS FOR MOBILE CLIENTS......Page 275
16.5.1 QUORUM-BASED PROTOCOLS......Page 276
16.6 REPLICA PLACEMENT......Page 277
16.7.1 REPLICATION MANAGEMENT IN CODA......Page 278
16.7.2 REPLICATION MANAGEMENT IN BAYOU......Page 279
16.7.3 GOSSIP ARCHITECTURE......Page 280
16.8 CONCLUDING REMARKS......Page 281
16.10 EXERCISES......Page 282
17.1 INTRODUCTION......Page 285
17.2 THEORETICAL FOUNDATIONS......Page 286
17.3.1 MUTUAL EXCLUSION ON A UNIDIRECTIONAL RING......Page 287
17.3.2 MUTUAL EXCLUSION ON A BIDIRECTIONAL ARRAY......Page 289
17.4 STABILIZING GRAPH COLORING......Page 291
Dag-generation algorithm......Page 293
17.5 STABILIZING SPANNING TREE PROTOCOL......Page 294
17.6 DISTRIBUTED RESET......Page 295
17.7 STABILIZING CLOCK SYNCHRONIZATION......Page 298
17.8 CONCLUDING REMARKS......Page 299
17.10 EXERCISES......Page 300
Part E: Real World Issues......Page 304
18.1.1 EVENT-DRIVEN SIMULATION......Page 305
18.2.1 THE CHALLENGES......Page 307
18.2.2 CORRECTNESS ISSUES......Page 309
18.4 OPTIMISTIC SIMULATION AND TIME WARP......Page 310
18.4.1 GLOBAL VIRTUAL TIME......Page 311
18.7 EXERCISES......Page 312
19.1 INTRODUCTION......Page 315
19.3 COMMON SECURITY ATTACKS......Page 316
19.4 ENCRYPTION......Page 317
19.5.1 CONFUSION AND DIFFUSION......Page 319
19.5.2 DES......Page 320
19.5.5 ONE-TIME PAD......Page 321
19.5.6 STREAM CIPHERS......Page 322
19.6 PUBLIC-KEY CRYPTOSYSTEMS......Page 323
19.6.1 THE RIVEST–SHAMIR–ADLEMAN (RSA) METHOD......Page 324
19.6.2 ELGAMAL CRYPTOSYSTEM......Page 325
19.7.1 SIGNATURES IN SECRET-KEY CRYPTOSYSTEMS......Page 326
19.8.1 BIRTHDAY ATTACK......Page 327
19.9 ELLIPTIC CURVE CRYPTOGRAPHY......Page 328
19.10.1 AUTHENTICATION SERVER FOR SECRET-KEY CRYPTOSYSTEMS......Page 329
19.11 DIGITAL CERTIFICATES......Page 330
19.12.1 KERBEROS......Page 331
19.12.2 PRETTY GOOD PRIVACY (PGP)......Page 332
19.12.3 SECURE SOCKET LAYER (SSL)......Page 333
19.13.1 VPN......Page 334
19.14 SHARING A SECRET......Page 335
19.17 EXERCISES......Page 336
PROGRAMMING EXERCISES......Page 338
20.2 ARCHITECTURE OF A SENSOR NODE......Page 340
20.2.2 ZIGBEE ENABLED SENSOR NODES......Page 341
20.2.3 TINYOS OPERATING SYSTEM......Page 343
20.3 THE CHALLENGES IN WIRELESS SENSOR NETWORKS......Page 345
20.3.1 ENERGY CONSERVATION......Page 346
20.3.7 SECURITY......Page 347
20.4.1 DIRECTED DIFFUSION......Page 348
20.4.3 PEGASIS......Page 349
20.5 TIME SYNCHRONIZATION USING REFERENCE BROADCAST......Page 350
20.5.1 REFERENCE BROADCAST......Page 351
20.6 LOCALIZATION ALGORITHMS......Page 352
20.6.3 ANCHOR-BASED RANGING......Page 353
20.7.1 SPIN FOR DATA SECURITY......Page 354
20.7.1.2 An Overview of mu TESLA......Page 355
20.8 SAMPLE APPLICATION: PURSUER–EVADER GAMES......Page 356
20.9 CONCLUDING REMARKS......Page 358
20.11 EXERCISES......Page 359
21.2 THE FIRST-GENERATION P2P SYSTEMS......Page 364
21.2.2 GNUTELLA......Page 365
21.3 THE SECOND-GENERATION P2P SYSTEMS......Page 366
21.3.2 CHORD......Page 367
21.3.3 CONTENT ADDRESSABLE NETWORK (CAN)......Page 369
21.3.4 PASTRY......Page 371
21.4 KOORDE AND DE BRUIJN GRAPH......Page 372
21.5 THE SMALL-WORLD PHENOMENON......Page 373
21.6 SKIP GRAPH......Page 375
21.7 REPLICATION MANAGEMENT......Page 377
21.9 CENSORSHIP RESISTANCE, ANONYMITY, AND ETHICAL ISSUES......Page 378
21.11 BIBLIOGRAPHIC NOTES......Page 379
EXERCISES......Page 380
Bibliography......Page 383