Comprehensive textbook resource on distributed systems - integrates foundational topics with advanced topics of contemporary importance within the field
Distributed Systems: Theory and Applications is organized around three layers of abstractions: networks, middleware tools, and application framework. It presents data consistency models suited for requirements of innovative distributed shared memory applications. The book also focuses on distributed processing of big data, representation of distributed knowledge and management of distributed intelligence via distributed agents. To aid in understanding how these concepts apply to real-world situations, the work presents a case study on building a P2P Integrated E-Learning system. Downloadable lecture slides are included to help professors and instructors convey key concepts to their students.
Additional topics discussed in Distributed Systems: Theory and Applications include: - Network issues and high-level communication tools - Software tools for implementations of distributed middleware. - Data sharing across distributed components through publish and subscribe-based message diffusion, gossip protocol, P2P architecture and distributed shared memory. - Consensus, distributed coordination, and advanced middleware for building large distributed applications - Distributed data and knowledge management - Autonomy in distributed systems, multi-agent architecture - Trust in distributed systems, distributed ledger, Blockchain and related technologies.
Researchers, industry professionals, and students in the fields of science, technology, and medicine will be able to use Distributed Systems: Theory and Applications as a comprehensive textbook resource for understanding distributed systems, the specifics behind the modern elements which relate to them, and their practical applications.
Table of Contents
About the Authors xv
Preface xvii
Acknowledgments xxi
Acronyms xxiii
1 Introduction 1
1.1 Advantages of Distributed Systems 1
1.2 Defining Distributed Systems 3
1.3 Challenges of a Distributed System 5
1.4 Goals of Distributed System 6
1.4.1 Single System View 7
1.4.2 Hiding Distributions 7
1.4.3 Degrees and Distribution of Hiding 9
1.4.4 Interoperability 10
1.4.5 Dynamic Reconfiguration 10
1.5 Architectural Organization 11
1.6 Organization of the Book 12
Bibliography 13
2 The Internet 15
2.1 Origin and Organization 15
2.1.1 ISPs and the Topology of the Internet 17
2.2 Addressing the Nodes 17
2.3 Network Connection Protocol 20
2.3.1 IP Protocol 22
2.3.2 Transmission Control Protocol 22
2.3.3 User Datagram Protocol 22
2.4 Dynamic Host Control Protocol 23
2.5 Domain Name Service 24
2.5.1 Reverse DNS Lookup 27
2.5.2 Client Server Architecture 30
2.6 Content Distribution Network 32
2.7 Conclusion 34
Exercises 34
Bibliography 35
3 Process to Process Communication 37
3.1 Communication Types and Interfaces 38
3.1.1 Sequential Type 38
3.1.2 Declarative Type 39
3.1.3 Shared States 40
3.1.4 Message Passing 41
3.1.5 Communication Interfaces 41
3.2 Socket Programming 42
3.2.1 Socket Data Structures 43
3.2.2 Socket Calls 44
3.3 Remote Procedure Call 48
3.3.1 Xml RPC 52
3.4 Remote Method Invocation 55
3.5 Conclusion 59
Exercises 59
Additional Web Resources 61
Bibliography 61
4 Microservices, Containerization, and MPI 63
4.1 Microservice Architecture 64
4.2 REST Requests and APIs 66
4.2.1 Weather Data Using REST API 67
4.3 Cross Platform Applications 68
4.4 Message Passing Interface 78
4.4.1 Process Communication Models 78
4.4.2 Programming with MPI 81
4.5 Conclusion 87
Exercises 88
Additional Internet Resources 89
Bibliography 89
5 Clock Synchronization and Event Ordering 91
5.1 The Notion of Clock Time 92
5.2 External Clock Based Mechanisms 93
5.2.1 Cristian’s Algorithm 93
5.2.2 Berkeley Clock Protocol 94
5.2.3 Network Time Protocol 95
5.2.3.1 Symmetric Mode of Operation 96
5.3 Events and Temporal Ordering 97
5.3.1 Causal Dependency 99
5.4 Logical Clock 99
5.5 Causal Ordering of Messages 106
5.6 Multicast Message Ordering 107
5.6.1 Implementing FIFO Multicast 110
5.6.2 Implementing Causal Ordering 112
5.6.3 Implementing Total Ordering 113
5.6.4 Reliable Multicast 114
5.7 Interval Events 115
5.7.1 Conceptual Neighborhood 116
5.7.2 Spatial Events 118
5.8 Conclusion 120
Exercises 121
Bibliography 123
6 Global States and Termination Detection 127
6.1 Cuts and Global States 127
6.1.1 Global States 132
6.1.2 Recording of Global States 134
6.1.3 Problem in Recording Global State 138
6.2 Liveness and Safety 140
6.3 Termination Detection 143
6.3.1 Snapshot Based Termination Detection 144
6.3.2 Ring Method 145
6.3.3 Tree Method 148
6.3.4 Weight Throwing Method 151
6.4 Conclusion 153
Exercises 154
Bibliography 156
7 Leader Election 157
7.1 Impossibility Result 158
7.2 Bully Algorithm 159
7.3 Ring-Based Algorithms 160
7.3.1 Circulate IDs All the Way 161
7.3.2 As Far as an ID Can Go 162
7.4 Hirschberg and Sinclair Algorithm 163
7.5 Distributed Spanning Tree Algorithm 167
7.5.1 Single Initiator Spanning Tree 167
7.5.2 Multiple Initiators Spanning Tree 170
7.5.3 Minimum Spanning Tree 176
7.6 Leader Election in Trees 176
7.6.1 Overview of the Algorithm 176
7.6.2 Activation Stage 177
7.6.3 Saturation Stage 178
7.6.4 Resolution Stage 179
7.6.5 Two Nodes Enter SATURATED State 180
7.7 Leased Leader Election 182
7.8 Conclusion 184
Exercises 185
Bibliography 187
8 Mutual Exclusion 189
8.1 System Model 190
8.2 Coordinator-Based Solution 192
8.3 Assertion-Based Solutions 192
8.3.1 Lamport’s Algorithm 192
8.3.2 Improvement to Lamport’s Algorithm 195
8.3.3 Quorum-Based Algorithms 196
8.4 Token-Based Solutions 203
8.4.1 Suzuki and Kasami’s Algorithm 203
8.4.2 Singhal’s Heuristically Aided Algorithm 206
8.4.3 Raymond’s Tree-Based Algorithm 212
8.5 Conclusion 214
Exercises 215
Bibliography 216
9 Agreements and Consensus 219
9.1 System Model 220
9.1.1 Failures in Distributed System 221
9.1.2 Problem Definition 222
9.1.3 Agreement Problem and Its Equivalence 223
9.2 Byzantine General Problem (BGP) 225
9.2.1 BGP Solution Using Oral Messages 228
9.2.2 Phase King Algorithm 232
9.3 Commit Protocols 233
9.3.1 Two-Phase Commit Protocol 234
9.3.2 Three-Phase Commit 238
9.4 Consensus 239
9.4.1 Consensus in Synchronous Systems 239
9.4.2 Consensus in Asynchronous Systems 241
9.4.3 Paxos Algorithm 242
9.4.4 Raft Algorithm 244
9.4.5 Leader Election 246
9.5 Conclusion 248
Exercises 249
Bibliography 250
10 Gossip Protocols 253
10.1 Direct Mail 254
10.2 Generic Gossip Protocol 255
10.3 Anti-entropy 256
10.3.1 Push-Based Anti-Entropy 257
10.3.2 Pull-Based Anti-Entropy 258
10.3.3 Hybrid Anti-Entropy 260
10.3.4 Control and Propagation in Anti-Entropy 260
10.4 Rumor-mongering Gossip 261
10.4.1 Analysis of Rumor Mongering 262
10.4.2 Fault-Tolerance 265
10.5 Implementation Issues 265
10.5.1 Network-Related Issues 266
10.6 Applications of Gossip 267
10.6.1 Peer Sampling 267
10.6.2 Failure Detectors 270
10.6.3 Distributed Social Networking 271
10.7 Gossip in IoT Communication 273
10.7.1 Context-Aware Gossip 273
10.7.2 Flow-Aware Gossip 274
10.7.2.1 Fire Fly Gossip 274
10.7.2.2 Trickle 275
10.8 Conclusion 278
Exercises 279
Bibliography 280
11 Message Diffusion Using Publish and Subscribe 283
11.1 Publish and Subscribe Paradigm 284
11.1.1 Broker Network 285
11.2 Filters and Notifications 287
11.2.1 Subscription and Advertisement 288
11.2.2 Covering Relation 288
11.2.3 Merging Filters 290
11.2.4 Algorithms 291
11.3 Notification Service 294
11.3.1 Siena 294
11.3.2 Rebeca 295
11.3.3 Routing of Notification 296
11.4 MQTT 297
11.5 Advanced Message Queuing Protocol 299
11.6 Effects of Technology on Performance 301
11.7 Conclusions 303
Exercises 304
Bibliography 305
12 Peer-to-Peer Systems 309
12.1 The Origin and the Definition of P2P 310
12.2 P2P Models 311
12.2.1 Routing in P2P Network 312
12.3 Chord Overlay 313
12.4 Pastry 321
12.5 Can 325
12.6 Kademlia 327
12.7 Conclusion 331
Exercises 332
Bibliography 333
13 Distributed Shared Memory 337
13.1 Multicore and S-DSM 338
13.1.1 Coherency by Delegation to a Central Server 339
13.2 Manycore Systems and S-DSM 340
13.3 Programming Abstractions 341
13.3.1 MapReduce 341
13.3.2 OpenMP 343
13.3.3 Merging Publish and Subscribe with DSM 345
13.4 Memory Consistency Models 347
13.4.1 Sequential Consistency 349
13.4.2 Linearizability or Atomic Consistency 351
13.4.3 Relaxed Consistency Models 352
13.4.3.1 Release Consistency 356
13.4.4 Comparison of Memory Models 357
13.5 DSM Access Algorithms 358
13.5.1 Central Sever Algorithm 359
13.5.2 Migration Algorithm 360
13.5.3 Read Replication Algorithm 361
13.5.4 Full Replication Algorithm 362
13.6 Conclusion 364
Exercises 364
Bibliography 367
14 Distributed Data Management 371
14.1 Distributed Storage Systems 372
14.1.1 Raid 372
14.1.2 Storage Area Networks 372
14.1.3 Cloud Storage 373
14.2 Distributed File Systems 375
14.3 Distributed Index 376
14.4 NoSQL Databases 377
14.4.1 Key-Value and Document Databases 378
14.4.1.1 MapReduce Algorithm 380
14.4.2 Wide Column Databases 381
14.4.3 Graph Databases 382
14.4.3.1 Pregel Algorithm 384
14.5 Distributed Data Analytics 386
14.5.1 Distributed Clustering Algorithms 388
14.5.1.1 Distributed K-Means Clustering Algorithm 388
14.5.2 Stream Clustering 391
14.5.2.1 BIRCH Algorithm 392
14.6 Conclusion 393
Exercises 394
Bibliography 395
15 Distributed Knowledge Management 399
15.1 Distributed Knowledge 400
15.2 Distributed Knowledge Representation 401
15.2.1 Resource Description Framework (RDF) 401
15.2.2 Web Ontology Language (OWL) 406
15.3 Linked Data 407
15.3.1 Friend of a Friend 407
15.3.2 DBpedia 408
15.4 Querying Distributed Knowledge 409
15.4.1 SPARQL Query Language 410
15.4.2 SPARQL Query Semantics 411
15.4.3 SPARQL Query Processing 413
15.4.4 Distributed SPARQL Query Processing 414
15.4.5 Federated and Peer-to-Peer SPARQL Query Processing 416
15.5 Data Integration in Distributed Sensor Networks 421
15.5.1 Semantic Data Integration 422
15.5.2 Data Integration in Constrained Systems 424
15.6 Conclusion 427
Exercises 428
Bibliography 429
16 Distributed Intelligence 433
16.1 Agents and Multi-Agent Systems 434
16.1.1 Agent Embodiment 436
16.1.2 Mobile Agents 436
16.1.3 Multi-Agent Systems 437
16.2 Communication in Agent-Based Systems 438
16.2.1 Agent Communication Protocols 439
16.2.2 Interaction Protocols 440
16.2.2.1 Request Interaction Protocol 441
16.3 Agent Middleware 441
16.3.1 FIPA Reference Model 442
16.3.2 FIPA Compliant Middleware 443
16.3.2.1 JADE: Java Agent Development Environment 443
16.3.2.2 MobileC 443
16.3.3 Agent Migration 444
16.4 Agent Coordination 445
16.4.1 Planning 447
16.4.1.1 Distributed Planning Paradigms 447
16.4.1.2 Distributed Plan Representation and Execution 448
16.4.2 Task Allocation 450
16.4.2.1 Contract-Net Protocol 450
16.4.2.2 Allocation of Multiple Tasks 452
16.4.3 Coordinating Through the Environment 453
16.4.3.1 Construct-Ant-Solution 455
16.4.3.2 Update-Pheromone 456
16.4.4 Coordination Without Communication 456
16.5 Conclusion 456
Exercises 457
Bibliography 459
17 Distributed Ledger 461
17.1 Cryptographic Techniques 462
17.2 Distributed Ledger Systems 464
17.2.1 Properties of Distributed Ledger Systems 465
17.2.2 A Framework for Distributed Ledger Systems 466
17.3 Blockchain 467
17.3.1 Distributed Consensus in Blockchain 468
17.3.2 Forking 470
17.3.3 Distributed Asset Tracking 471
17.3.4 Byzantine Fault Tolerance and Proof of Work 472
17.4 Other Techniques for Distributed Consensus 473
17.4.1 Alternative Proofs 473
17.4.2 Non-linear Data Structures 474
17.4.2.1 Tangle 474
17.4.2.2 Hashgraph 476
17.5 Scripts and Smart Contracts 480
17.6 Distributed Ledgers for Cyber-Physical Systems 483
17.6.1 Layered Architecture 484
17.6.2 Smart Contract in Cyber-Physical Systems 486
17.7 Conclusion 486
Exercises 487
Bibliography 488
18 Case Study 491
18.1 Collaborative E-Learning Systems 492
18.2 P2P E-Learning System 493
18.2.1 Web Conferencing Versus P2P-IPS 495
18.3 P2P Shared Whiteboard 497
18.3.1 Repainting Shared Whiteboard 497
18.3.2 Consistency of Board View at Peers 498
18.4 P2P Live Streaming 500
18.4.1 Peer Joining 500
18.4.2 Peer Leaving 503
18.4.3 Handling “Ask Doubt” 504
18.5 P2P-IPS for Stored Contents 504
18.5.1 De Bruijn Graphs for DHT Implementation 505
18.5.2 Node Information Structure 507
18.5.2.1 Join Example 510
18.5.3 Leaving of Peers 510
18.6 Searching, Sharing, and Indexing 511
18.6.1 Pre-processing of Files 511
18.6.2 File Indexing 512
18.6.3 File Lookup and Download 512
18.7 Annotations and Discussion Forum 513
18.7.1 Annotation Format 513
18.7.2 Storing Annotations 514
18.7.3 Audio and Video Annotation 514
18.7.4 PDF Annotation 514
18.7.5 Posts, Comments, and Announcements 514
18.7.6 Synchronization of Posts and Comments 515
18.7.6.1 Epidemic Dissemination 516
18.7.6.2 Reconciliation 516
18.8 Simulation Results 516
18.8.1 Live Streaming and Shared Whiteboard 517
18.8.2 De Bruijn Overlay 518
18.9 Conclusion 520
Bibliography 521
Index 525
