Distributed Systems
Description
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.
More details
Other editions
Additional editions
Persons
Ratan K. Ghosh, PhD, is formerly a Professor of the Department of CSE at IIT Kanpur. At present, he is affiliated to BITS-Mesra as an Adjunct Professor and to Kaziranga University-Jorhat as a Distinguished Visiting Professor, Mentor and Advisor. He is a Life Member of ACM. He authored the Springer Research Monograph titled Wireless Networking and Mobile Data Management (April 2017).
Hiranmay Ghosh, PhD, is a former Adviser and Principal Scientist of TCS Research. He received his PhD degree from IIT-Delhi and his B.Tech. degree from Calcutta University. He is a Senior Member of IEEE, Life Member of IUPRAI, and a Member of ACM. He authored the Wiley title Computational Models for Cognitive Vision (2020) and co-authored of the CRC Press title Multimedia Ontology: Representation and Applications (2015).
Content
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
1
Introduction
A distributed system consists of many independent units, each performing a different function. The units work in coordination with each other to realize the system's goals. We find many examples of distributed systems in nature. For instance, a human body consists of several autonomous components such as eyes and ears, hands and legs, and other internal organs. Yet, coordinated by the brain, it behaves as a single coherent entity. Some distributed systems may have hierarchic organizations. For example, the coordinated interaction among human beings performing various roles realizes the goals of human society. We find such well-orchestrated activities in lower forms of animals too. For example, in a beehive an ensemble of bees exhibit coordinated and consistent social behaviors fulfilling their goals of foraging.
Inspired by nature, researchers have developed a distributed systems paradigm for solving complex multi-dimensional computation problems. This book aims to provide a narrative for the various aspects of distributed systems and the computational models for interactions at multiple levels of abstractions. We also describe the application of such models in realizing practical distributed systems. In our journey through the book, we begin with the low-level interaction of the system components to achieve performance through parallelism and concurrency. We progressively ascend to higher levels of abstractions to address the issues of knowledge, autonomy, and trust, which are essential for large distributed systems spanning multiple administrative domains.
1.1 Advantages of Distributed Systems
A distributed system offers many advantages. Let us illustrate them with a simple example. Figure 1.1 depicts a distributed system for evaluation of simple arithmetic expressions. The expression-evaluator in the system divides the problem into smaller tasks of multiplications and additions and engages other modules, namely, a set of adders and multipliers, to solve them. Hosting the modules on different computers connected over a network is possible. It schedules the activities of those modules and communicates the final result to the user. We can notice several advantages of a distributed computing even through this trivial example:
Figure 1.1 Illustrating distributed computing.
- Performance enhancement: The system may engage multiple components to perform subtasks, e.g., multiplications, in parallel, resulting in performance improvement. However, the distribution of the components over multiple hardware elements causes increased communication overheads. So, an analysis of trade-off is necessary between parallel computation and communication.
- Specialization and autonomy: Each module may be designed independently for performing a specific task, e.g., addition or multiplication. A component can implement any specific algorithm irrespective of the type of algorithms deployed in the other modules. So, localization of task-dependent knowledge and the local optimization of the modules for performance enhancements are possible. It simplifies the design of the system. The modules can even be implemented on disparate hardware and in different programming environments by various developers. A change in one module does not affect others, so long as the interfaces remain unchanged.
- Geographic distribution and transparency: It is possible to locate the components on machines at various geographical locations and administrative domains. The geographical distribution of the components is generally transparent to the applications, introducing flexibility of dynamic redistribution. For example, the a piece of computation can be scheduled on a computing node that has the least load at a given point of time, and can be shifted to another node in case of a failure. It results in reuse and optimal utilization of the resources. As another example, the replicas of a storage system can be distributed across multiple geographical locations to guard against accidental data loss.
- Dynamic binding and optimization: A distributed system can have a pool of similar computational resources, such as adders and multipliers. These resources may be dynamically associated with different computing problems at different points in time. Further, even similar resources, like the multipliers, may have different performance metrics, like speed and accuracy. The system can choose an optimal set of modules in a specific problem context. Such optimum and dynamic binding of the resources leads to improvement of overall system performance.
- Fault tolerance: The availability of a pool of similar resources aids in fault tolerance in the system. If one of the system components fails, then the task can migrate to another component. The system can experience a graceful performance degradation in such cases, rather than a system failure.
- Openness, scalability, and dynamic reconfigurability: A distributed system can be designed as an open system, where individual components can interact with a set of standard protocols. It facilitates the independent design of the components. Loose coupling between the system components helps in scalability. Further, we can replace deprecated components by new components without shutting down a system.
1.2 Defining Distributed Systems
Leslie Lamport's seminal work [Lamport 2019] laid down the theoretical foundations of time, clock, and event ordering in a distributed system. Lamport realized that the concept of sequential time and system state does not work in distributed systems. A failure in a distributed system is one of the toughest problems to understand. The failure is meaningful only in the context of time. Whether a computing system or a link has failed is indistinguishable from an unusually late response. Lamport recognized the importance of failure detection and recovery in a distributed system through the following famous quip [Malkh 2013]:
"A distributed system is one in which the failure of a computer you didn't even know existed can render your own computer unusable."
Understandably, fault tolerance [Neiger and Toueg 1988, Xiong et al. 2009], which includes detection of failures and recovery from faults, is a dominant area of research in distributed systems.
There are many technical-sounding definitions, but all seem to converge on the importance of fault tolerance in distributed systems. We plan to discuss fault tolerance in this book sometime later. However, to get a flavor of different ways of defining a distributed system, let us examine a few of those found in the literature [Kshemkalyani and Singhal 2011].
Definition 1.1 (Collection and coordination): A distributed system is a collection of computers not sharing a common memory or a common physical clock that communicates by messages over a communication network and where each computer has its memory and runs on its OS. Typically computers are semi-automatic, loosely coupled when they cooperate to address a problem collectively.
Definition 1.2 (Single system view): A collection of independent computers that appear to the users of the system as a single coherent computer.
Definition 1.3 (Collection): A term used to describe a wide range of computer systems from a weakly coupled system such as a wide area network to strongly coupled systems such local area network, to very strongly coupled multiprocessor systems.
The running idea behind all three definitions stated earlier is to capture certain basic characteristics of a distributed system; namely,
- There is no common clock in a distributed system.
- It consists of several networked autonomous computers, each having its clock, memory, and OS.
- It does not have a shared memory.
- The computers of a distributed can communicate and coordinate through message passing over network links.
However, we feel that the definitions are still inadequate in missing out on two key aspects of Lamport's observation of a distributed system. We propose the following new definition.
Definition 1.4 (Proposed definition): A distributed system consists of several independent, geographically dispersed, and networked computing elements such as computers, smartphones, sensors, actuators, and embedded electronic devices. These devices communicate among themselves through message passing to coordinate and cooperate in satisfying common computing goals, notwithstanding the occasional failures of a few links or devices.
The proposed definition covers the basic characteristics of a collection of networked computing devices. It indicates that a collections of independent components integrated as a unified system is a distributed system that
- Subsumes Definitions 1.3 and 1.2,
- Covers coordination aspect as in Definition 1.1,
- Includes fault tolerance and message passing aspects of Lamport's observation.
1.3 Challenges of a Distributed System
Some of the well-understood bottlenecks for implementing a distributed system are the following:
- Centralized algorithms: A single computer is responsible for program control decisions. These algorithms are suitable for client-server model of computation where a server may be overwhelmed by many...
