+353-1-416-8900REST OF WORLD
+44-20-3973-8888REST OF WORLD
1-917-300-0470EAST COAST U.S
1-800-526-8630U.S. (TOLL FREE)

Distributed Systems. Theory and Applications. Edition No. 1

  • Book

  • 560 Pages
  • February 2023
  • John Wiley and Sons Ltd
  • ID: 5841851
Distributed Systems

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

Authors

Ratan K. Ghosh IIT Kanpur. Hiranmay Ghosh IIT Delhi; Calcutta University.