Distributed Systems: Principles and Paradigms

CONTENTS......Page 3
PREFACE......Page 8
A GUIDE TO USING THIS BOOK......Page 9
DISTRIBUTED SYSTEMS PRINCIPLES AND PARADIGMS......Page 11
1  INTRODUCTION......Page 12
1.1  DEFINITION OF A  DISTRIBUTED SYSTEM......Page 13
1.2.2  Transparency......Page 14
1.2.3  Openness......Page 16
1.2.4  Scalability......Page 17
1.3.1  Multiprocessors......Page 20
1.3.2  Homogeneous Multicomputer Systems......Page 21
1.3.3  Heterogeneous Multicomputer Systems......Page 22
1.4.1  Distributed Operating Systems......Page 23
1.4.2  Network Operating Systems......Page 28
1.4.3  Middleware......Page 30
1.5.1  Clients and Servers......Page 33
1.5.2  Application Layering......Page 35
1.5.3  Client-Server Architectures......Page 37
1.6  SUMMARY......Page 38
2  COMMUNICATION......Page 40
2.1  LAYERED PROTOCOLS......Page 41
2.1.1  Lower-Level Protocols......Page 42
2.1.2  Transport Protocols......Page 43
2.1.3  Higher-Level Protocols......Page 45
2.2.1  Basic RPC Operation......Page 46
2.2.2  Parameter Passing......Page 48
2.2.3  Extended RPC Models......Page 50
2.2.4  Example: DCE RPC......Page 52
2.3  REMOTE OBJECT INVOCATION......Page 54
2.3.1  Distributed Objects......Page 55
2.3.2  Binding a Client to an Object......Page 56
2.3.4  Parameter Passing......Page 57
2.3.5  Example 1: DCE Remote Objects......Page 58
2.3.6  Example 2: Java RMI......Page 59
2.4.1  Persistence and Synchronicity in Communication......Page 61
2.4.2  Message-Oriented Transient Communication......Page 65
2.4.3  Message-Oriented Persistent Communication......Page 67
2.4.4  Exaple: IBM MQSeries......Page 70
2.5  STREAM-ORIENTED COMMUNICATION......Page 72
2.5.1  Support for Continious Media......Page 73
2.5.2  Streams and Quality of Service......Page 74
2.5.3  Stream Synchronization......Page 76
2.6  SUMMARY......Page 78
3  PROCESSES......Page 80
3.1.1  Introduction to Threads......Page 81
3.1.2  Threads in Distributed Systems......Page 83
3.2.1  User Interfaces......Page 85
3.2.2  Client-Side Software for Distribution Transparency......Page 86
3.3.1  General Design Issues......Page 87
3.3.2  Object Servers......Page 89
3.4.1  Approaches to Code Migration......Page 92
3.4.2  Migration and Local Resources......Page 94
3.4.3  Migration in Heterogeneous Systems......Page 95
3.4.4  Example: D' Agents......Page 97
3.5.1  Software Agents in Distributed Systems......Page 99
3.5.2  Agent Technology......Page 100
3.6  SUMMARY......Page 102
4  NAMING......Page 104
4.1.1  Names, Identifiers, and Addresses......Page 105
4.1.2  Name Resolution......Page 107
4.1.3  The Implementation of a Name Space......Page 110
4.1.4  Example: The Domain Name System......Page 113
4.1.5  Example: X.500......Page 116
4.2.1  Naming versus Locating Entities......Page 118
4.2.2  Simple Solutions......Page 119
4.2.4  Hierarchical Approaches......Page 121
4.3.1  The Problem of Unreferenced Objects......Page 125
4.3.2  Reference Counting......Page 126
4.3.3  Reference Listing......Page 128
4.3.4  Identifying Unreachable Entities......Page 129
4.4  SUMMARY......Page 132
5  SYNCHRONIZATION......Page 133
5.1.1  Physical Clocks......Page 134
5.1.3  Use of Synchronized Clocks......Page 138
5.2.1  Lamport timestamps......Page 139
5.2.2  Vector timestamps......Page 141
5.3  GLOBAL STATE......Page 142
5.4.2  A Ring Algorithm......Page 144
5.5.1  A Centralized Algorithm......Page 145
5.5.2  A Distributed Algorithm......Page 146
5.5.3  A Token Ring Algorithm......Page 147
5.6  DISTRIBUTED TRANSACTIONS......Page 148
5.6.1  The Transaction Model......Page 149
5.6.2  Classification of Transactions......Page 150
5.6.3  Implementation......Page 152
5.6.4  Concurrency Control......Page 153
5.7  SUMMARY......Page 157
6  CONSISTENCY AND REPLICATION......Page 158
6.1.2  Object Replication......Page 159
6.2  DATA-CENTRIC CONSISTENCY MODELS......Page 161
6.2.1  Strict Consistency......Page 162
6.2.2  Linearizability and Sequential Consistency......Page 163
6.2.3  Causal Consistency......Page 165
6.2.4  FIFO Consistency......Page 166
6.2.5  Weak Consistency......Page 167
6.2.6  Release Consistency......Page 168
6.2.7  Entry Consistency......Page 169
6.2.8  Summary of Consistency Models......Page 170
6.3.1  Eventual Consistency......Page 171
6.3.2  Monotonic Reads......Page 172
6.3.3  Monotonic Writes......Page 173
6.3.5  Writes Follow Reads......Page 174
6.3.6  Implementation......Page 175
6.4.1  Replica Pleacement......Page 176
6.4.2  Update Propagation......Page 178
6.4.3  Epidemic Protocols......Page 180
6.5.1  Primary-Based Protocols......Page 181
6.5.2  Replicated-Write Protocols......Page 183
6.5.3  Cache-Coherence Protocols......Page 185
6.6.1  Orca......Page 186
6.6.2  Causally-Consistent Lazy Replication......Page 189
6.7 SUMMARY......Page 191
7  FAULT TOLERANCE......Page 193
7.1.1  Basis Concepts......Page 194
7.1.2  Failure Models......Page 195
7.1.3  Failure Masking by Redundancy......Page 196
7.2.1  Design Issues......Page 197
7.2.3  Agreement in Faulty Systems......Page 198
7.3.2  RPC Semantics in the Presence of Failures......Page 200
7.4.1  Basic Reliable-Multicasting Schemes......Page 203
7.4.2  Scalability in Reliable Multicasting......Page 204
7.4.3  Atomic Multicast......Page 206
7.5.1  Two-Phase Commit......Page 209
7.5.2  Three-Phase Commit......Page 212
7.6.1  Introduction......Page 213
7.6.2  Checkpointing......Page 215
7.6.3 Message Logging......Page 216
7.7  SUMMARY......Page 218
8  SECURITY......Page 219
8.1.1  Security Threats, Policies, and Mechanisms......Page 220
8.1.2  Design Issues......Page 223
8.1.3  Cryptography......Page 225
8.2.1  Authentication......Page 229
8.2.2  Message Integrity and Confidentiality......Page 233
8.2.3  Secure Group Communication......Page 235
8.3.1  General Issues in Access Control......Page 236
8.3.2  Firewalls......Page 238
8.3.3  Secure Mobile Code......Page 239
8.4.1  Key Management......Page 243
8.4.2  Secure Group Management......Page 245
8.4.3  Authorization Management......Page 246
8.6  EXAMPLE: SESAME......Page 249
8.6.1  SESAME Components......Page 250
8.6.2  Privilege Attribute Certificates (PACs)......Page 251
8.7.1  Electronic Payment Systems......Page 252
8.7.2  Security in Electronic Payment Systems......Page 253
8.7.3  Example Protocols......Page 255
8.8  SUMMARY......Page 257
9  DISTRIBUTED OBJECT-BASED SYSTEMS......Page 259
9.1.1  Overview of CORBA......Page 260
9.1.2  Communication......Page 263
9.1.3  Processes......Page 267
9.1.4  Naming......Page 270
9.1.6  Caching and Replication......Page 272
9.1.7  Fault Tolerance......Page 273
9.1.8  Security......Page 274
9.2  DISTRIBUTED COM......Page 275
9.2.1  Overview of DCOM......Page 276
9.2.2  Communication......Page 278
9.2.3  Processes......Page 280
9.2.4  Naming......Page 281
9.2.7  Fault Tolerance......Page 283
9.2.8  Security......Page 284
9.3.1  Overview of Globe......Page 285
9.3.2  Communication......Page 289
9.3.3  Processes......Page 290
9.3.4  Naming......Page 291
9.3.5  Synchronization......Page 292
9.3.6  Replication......Page 293
9.3.8  Security......Page 294
9.4  COMPARISON OF CORBA, DCOM, AND GLOBE......Page 295
9.4.3  Processes......Page 296
9.4.6  Caching and Replication......Page 297
9.4.8  Security......Page 298
9.5  SUMMARY......Page 299
10  DISTRIBUTED FILE SYSTEMS......Page 300
10.1.1  Overview of NFS......Page 301
10.1.2  Communication......Page 303
10.1.4  Naming......Page 304
10.1.5  Synchronization......Page 308
10.1.6  Caching and Replication......Page 310
10.1.7  Fault Tolerance......Page 311
10.1.8  Security......Page 313
10.2.1  Overview of Coda......Page 315
10.2.2  Communication......Page 316
10.2.4  Naming......Page 317
10.2.5  Synchronization......Page 318
10.2.6  Caching and Replication......Page 320
10.2.7  Fault Tolerance......Page 322
10.2.8  Security......Page 323
10.3.1  Plan 9: Resources Unifled to Files......Page 324
10.3.2  XFS: Serverless File System......Page 327
10.3.3  SFS: Scalable Security......Page 330
10.4.3  Processes......Page 332
10.4.6  Caching and Replication......Page 333
10.5  SUMMARY......Page 334
11  DISTRIBUTED DOCUMENT-BASED SYSTEMS......Page 336
11.1.1  Overview of WWW......Page 337
11.1.2  Communication......Page 341
11.1.3  Processes......Page 344
11.1.4  Naming......Page 347
11.1.5  Synchronization......Page 348
11.1.6  Caching and Replication......Page 349
11.1.8  Security......Page 351
11.2.1  Overview of Lotus Notes......Page 352
11.2.3  Processes......Page 353
11.2.4  Naming......Page 354
11.2.6  Replication......Page 355
11.2.8  Security......Page 357
11.3  COMPARISON OF WWW AND LOTUS NOTES......Page 358
11.4  SUMMARY......Page 360
12  DISTRIBUTED COORDINATION-BASE SYSTEMS......Page 362
12.1  INTRODUCTION TO COORDINATION MODELS......Page 363
12.2.1  Overview of TIB/Rendezvous......Page 364
12.2.2  Communication......Page 365
12.2.4  Naming......Page 367
12.2.5  Synchronization......Page 368
12.2.7  Fault Tolerance......Page 369
12.2.8  Security......Page 370
12.3.1  Overview of Jini......Page 371
12.3.2  Communication......Page 372
12.3.3  Processes......Page 373
12.3.4  Naming......Page 375
12.3.5  Synchronization......Page 376
12.3.8  Security......Page 377
12.4  COMPARISON OF TIB/RENDEZVOUS AND JINI......Page 378
12.5  SUMMARY......Page 379
13.1.1  Introduction and General Works......Page 381
13.1.3  Processes......Page 382
13.1.5  Synchronization......Page 383
13.1.7  Fault Tolerance......Page 384
13.1.9  Distributed Object-Based Systems......Page 385
13.1.11  Distributed Document-Based Systems......Page 386
13.2  ALPHABETICAL BIBLOGRAPHY......Page 387
INDEX......Page 404
ABOUT THE AUTHORS......Page 415