Distributed Systems: Theory and Applications

ISBN-13: 9781119825937 / Angielski / Twarda / 2023 / 450 str.

Ratan K. Ghosh; Hiranmay Ghosh

Spis treści

About the Authors xvPreface xviiAcknowledgments xxiAcronyms xxiii1 Introduction 11.1 Advantages of Distributed Systems 11.2 Defining Distributed Systems 31.3 Challenges of a Distributed System 51.4 Goals of Distributed System 61.4.1 Single System View 71.4.2 Hiding Distributions 71.4.3 Degrees and Distribution of Hiding 91.4.4 Interoperability 101.4.5 Dynamic Reconfiguration 101.5 Architectural Organization 111.6 Organization of the Book 12Bibliography 132 The Internet 152.1 Origin and Organization 152.1.1 ISPs and the Topology of the Internet 172.2 Addressing the Nodes 172.3 Network Connection Protocol 202.3.1 IP Protocol 222.3.2 Transmission Control Protocol 222.3.3 User Datagram Protocol 222.4 Dynamic Host Control Protocol 232.5 Domain Name Service 242.5.1 Reverse DNS Lookup 272.5.2 Client Server Architecture 302.6 Content Distribution Network 322.7 Conclusion 34Exercises 34Bibliography 353 Process to Process Communication 373.1 Communication Types and Interfaces 383.1.1 Sequential Type 383.1.2 Declarative Type 393.1.3 Shared States 403.1.4 Message Passing 413.1.5 Communication Interfaces 413.2 Socket Programming 423.2.1 Socket Data Structures 433.2.2 Socket Calls 443.3 Remote Procedure Call 483.3.1 Xml RPC 523.4 Remote Method Invocation 553.5 Conclusion 59Exercises 59Additional Web Resources 61Bibliography 614 Microservices, Containerization, and MPI 634.1 Microservice Architecture 644.2 REST Requests and APIs 664.2.1 Weather Data Using REST API 674.3 Cross Platform Applications 684.4 Message Passing Interface 784.4.1 Process Communication Models 784.4.2 Programming with MPI 814.5 Conclusion 87Exercises 88Additional Internet Resources 89Bibliography 895 Clock Synchronization and Event Ordering 915.1 The Notion of Clock Time 925.2 External Clock Based Mechanisms 935.2.1 Cristian's Algorithm 935.2.2 Berkeley Clock Protocol 945.2.3 Network Time Protocol 955.2.3.1 Symmetric Mode of Operation 965.3 Events and Temporal Ordering 975.3.1 Causal Dependency 995.4 Logical Clock 995.5 Causal Ordering of Messages 1065.6 Multicast Message Ordering 1075.6.1 Implementing FIFO Multicast 1105.6.2 Implementing Causal Ordering 1125.6.3 Implementing Total Ordering 1135.6.4 Reliable Multicast 1145.7 Interval Events 1155.7.1 Conceptual Neighborhood 1165.7.2 Spatial Events 1185.8 Conclusion 120Exercises 121Bibliography 1236 Global States and Termination Detection 1276.1 Cuts and Global States 1276.1.1 Global States 1326.1.2 Recording of Global States 1346.1.3 Problem in Recording Global State 1386.2 Liveness and Safety 1406.3 Termination Detection 1436.3.1 Snapshot Based Termination Detection 1446.3.2 Ring Method 1456.3.3 Tree Method 1486.3.4 Weight Throwing Method 1516.4 Conclusion 153Exercises 154Bibliography 1567 Leader Election 1577.1 Impossibility Result 1587.2 Bully Algorithm 1597.3 Ring-Based Algorithms 1607.3.1 Circulate IDs All the Way 1617.3.2 As Far as an ID Can Go 1627.4 Hirschberg and Sinclair Algorithm 1637.5 Distributed Spanning Tree Algorithm 1677.5.1 Single Initiator Spanning Tree 1677.5.2 Multiple Initiators Spanning Tree 1707.5.3 Minimum Spanning Tree 1767.6 Leader Election in Trees 1767.6.1 Overview of the Algorithm 1767.6.2 Activation Stage 1777.6.3 Saturation Stage 1787.6.4 Resolution Stage 1797.6.5 Two Nodes Enter SATURATED State 1807.7 Leased Leader Election 1827.8 Conclusion 184Exercises 185Bibliography 1878 Mutual Exclusion 1898.1 System Model 1908.2 Coordinator-Based Solution 1928.3 Assertion-Based Solutions 1928.3.1 Lamport's Algorithm 1928.3.2 Improvement to Lamport's Algorithm 1958.3.3 Quorum-Based Algorithms 1968.4 Token-Based Solutions 2038.4.1 Suzuki and Kasami's Algorithm 2038.4.2 Singhal's Heuristically Aided Algorithm 2068.4.3 Raymond's Tree-Based Algorithm 2128.5 Conclusion 214Exercises 215Bibliography 2169 Agreements and Consensus 2199.1 System Model 2209.1.1 Failures in Distributed System 2219.1.2 Problem Definition 2229.1.3 Agreement Problem and Its Equivalence 2239.2 Byzantine General Problem (BGP) 2259.2.1 BGP Solution Using Oral Messages 2289.2.2 Phase King Algorithm 2329.3 Commit Protocols 2339.3.1 Two-Phase Commit Protocol 2349.3.2 Three-Phase Commit 2389.4 Consensus 2399.4.1 Consensus in Synchronous Systems 2399.4.2 Consensus in Asynchronous Systems 2419.4.3 Paxos Algorithm 2429.4.4 Raft Algorithm 2449.4.5 Leader Election 2469.5 Conclusion 248Exercises 249Bibliography 25010 Gossip Protocols 25310.1 Direct Mail 25410.2 Generic Gossip Protocol 25510.3 Anti-entropy 25610.3.1 Push-Based Anti-Entropy 25710.3.2 Pull-Based Anti-Entropy 25810.3.3 Hybrid Anti-Entropy 26010.3.4 Control and Propagation in Anti-Entropy 26010.4 Rumor-mongering Gossip 26110.4.1 Analysis of Rumor Mongering 26210.4.2 Fault-Tolerance 26510.5 Implementation Issues 26510.5.1 Network-Related Issues 26610.6 Applications of Gossip 26710.6.1 Peer Sampling 26710.6.2 Failure Detectors 27010.6.3 Distributed Social Networking 27110.7 Gossip in IoT Communication 27310.7.1 Context-Aware Gossip 27310.7.2 Flow-Aware Gossip 27410.7.2.1 Fire Fly Gossip 27410.7.2.2 Trickle 27510.8 Conclusion 278Exercises 279Bibliography 28011 Message Diffusion Using Publish and Subscribe 28311.1 Publish and Subscribe Paradigm 28411.1.1 Broker Network 28511.2 Filters and Notifications 28711.2.1 Subscription and Advertisement 28811.2.2 Covering Relation 28811.2.3 Merging Filters 29011.2.4 Algorithms 29111.3 Notification Service 29411.3.1 Siena 29411.3.2 Rebeca 29511.3.3 Routing of Notification 29611.4 MQTT 29711.5 Advanced Message Queuing Protocol 29911.6 Effects of Technology on Performance 30111.7 Conclusions 303Exercises 304Bibliography 30512 Peer-to-Peer Systems 30912.1 The Origin and the Definition of P2P 31012.2 P2P Models 31112.2.1 Routing in P2P Network 31212.3 Chord Overlay 31312.4 Pastry 32112.5 Can 32512.6 Kademlia 32712.7 Conclusion 331Exercises 332Bibliography 33313 Distributed Shared Memory 33713.1 Multicore and S-DSM 33813.1.1 Coherency by Delegation to a Central Server 33913.2 Manycore Systems and S-DSM 34013.3 Programming Abstractions 34113.3.1 MapReduce 34113.3.2 OpenMP 34313.3.3 Merging Publish and Subscribe with DSM 34513.4 Memory Consistency Models 34713.4.1 Sequential Consistency 34913.4.2 Linearizability or Atomic Consistency 35113.4.3 Relaxed Consistency Models 35213.4.3.1 Release Consistency 35613.4.4 Comparison of Memory Models 35713.5 DSM Access Algorithms 35813.5.1 Central Sever Algorithm 35913.5.2 Migration Algorithm 36013.5.3 Read Replication Algorithm 36113.5.4 Full Replication Algorithm 36213.6 Conclusion 364Exercises 364Bibliography 36714 Distributed Data Management 37114.1 Distributed Storage Systems 37214.1.1 Raid 37214.1.2 Storage Area Networks 37214.1.3 Cloud Storage 37314.2 Distributed File Systems 37514.3 Distributed Index 37614.4 NoSQL Databases 37714.4.1 Key-Value and Document Databases 37814.4.1.1 MapReduce Algorithm 38014.4.2 Wide Column Databases 38114.4.3 Graph Databases 38214.4.3.1 Pregel Algorithm 38414.5 Distributed Data Analytics 38614.5.1 Distributed Clustering Algorithms 38814.5.1.1 Distributed K-Means Clustering Algorithm 38814.5.2 Stream Clustering 39114.5.2.1 BIRCH Algorithm 39214.6 Conclusion 393Exercises 394Bibliography 39515 Distributed Knowledge Management 39915.1 Distributed Knowledge 40015.2 Distributed Knowledge Representation 40115.2.1 Resource Description Framework (RDF) 40115.2.2 Web Ontology Language (OWL) 40615.3 Linked Data 40715.3.1 Friend of a Friend 40715.3.2 DBpedia 40815.4 Querying Distributed Knowledge 40915.4.1 SPARQL Query Language 41015.4.2 SPARQL Query Semantics 41115.4.3 SPARQL Query Processing 41315.4.4 Distributed SPARQL Query Processing 41415.4.5 Federated and Peer-to-Peer SPARQL Query Processing 41615.5 Data Integration in Distributed Sensor Networks 42115.5.1 Semantic Data Integration 42215.5.2 Data Integration in Constrained Systems 42415.6 Conclusion 427Exercises 428Bibliography 42916 Distributed Intelligence 43316.1 Agents and Multi-Agent Systems 43416.1.1 Agent Embodiment 43616.1.2 Mobile Agents 43616.1.3 Multi-Agent Systems 43716.2 Communication in Agent-Based Systems 43816.2.1 Agent Communication Protocols 43916.2.2 Interaction Protocols 44016.2.2.1 Request Interaction Protocol 44116.3 Agent Middleware 44116.3.1 FIPA Reference Model 44216.3.2 FIPA Compliant Middleware 44316.3.2.1 JADE: Java Agent Development Environment 44316.3.2.2 MobileC 44316.3.3 Agent Migration 44416.4 Agent Coordination 44516.4.1 Planning 44716.4.1.1 Distributed Planning Paradigms 44716.4.1.2 Distributed Plan Representation and Execution 44816.4.2 Task Allocation 45016.4.2.1 Contract-Net Protocol 45016.4.2.2 Allocation of Multiple Tasks 45216.4.3 Coordinating Through the Environment 45316.4.3.1 Construct-Ant-Solution 45516.4.3.2 Update-Pheromone 45616.4.4 Coordination Without Communication 45616.5 Conclusion 456Exercises 457Bibliography 45917 Distributed Ledger 46117.1 Cryptographic Techniques 46217.2 Distributed Ledger Systems 46417.2.1 Properties of Distributed Ledger Systems 46517.2.2 A Framework for Distributed Ledger Systems 46617.3 Blockchain 46717.3.1 Distributed Consensus in Blockchain 46817.3.2 Forking 47017.3.3 Distributed Asset Tracking 47117.3.4 Byzantine Fault Tolerance and Proof of Work 47217.4 Other Techniques for Distributed Consensus 47317.4.1 Alternative Proofs 47317.4.2 Non-linear Data Structures 47417.4.2.1 Tangle 47417.4.2.2 Hashgraph 47617.5 Scripts and Smart Contracts 48017.6 Distributed Ledgers for Cyber-Physical Systems 48317.6.1 Layered Architecture 48417.6.2 Smart Contract in Cyber-Physical Systems 48617.7 Conclusion 486Exercises 487Bibliography 48818 Case Study 49118.1 Collaborative E-Learning Systems 49218.2 P2P E-Learning System 49318.2.1 Web Conferencing Versus P2P-IPS 49518.3 P2P Shared Whiteboard 49718.3.1 Repainting Shared Whiteboard 49718.3.2 Consistency of Board View at Peers 49818.4 P2P Live Streaming 50018.4.1 Peer Joining 50018.4.2 Peer Leaving 50318.4.3 Handling "Ask Doubt" 50418.5 P2P-IPS for Stored Contents 50418.5.1 De Bruijn Graphs for DHT Implementation 50518.5.2 Node Information Structure 50718.5.2.1 Join Example 51018.5.3 Leaving of Peers 51018.6 Searching, Sharing, and Indexing 51118.6.1 Pre-processing of Files 51118.6.2 File Indexing 51218.6.3 File Lookup and Download 51218.7 Annotations and Discussion Forum 51318.7.1 Annotation Format 51318.7.2 Storing Annotations 51418.7.3 Audio and Video Annotation 51418.7.4 PDF Annotation 51418.7.5 Posts, Comments, and Announcements 51418.7.6 Synchronization of Posts and Comments 51518.7.6.1 Epidemic Dissemination 51618.7.6.2 Reconciliation 51618.8 Simulation Results 51618.8.1 Live Streaming and Shared Whiteboard 51718.8.2 De Bruijn Overlay 51818.9 Conclusion 520Bibliography 521Index 525

O autorze

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).