Distributed Systems: Theory and Applications

Cover
Title Page
Copyright
Contents
About the Authors
Preface
Acknowledgments
Acronyms
Chapter 1 Introduction
1.1 Advantages of Distributed Systems
1.2 Defining Distributed Systems
1.3 Challenges of a Distributed System
1.4 Goals of Distributed System
1.4.1 Single System View
1.4.2 Hiding Distributions
1.4.3 Degrees and Distribution of Hiding
1.4.4 Interoperability
1.4.5 Dynamic Reconfiguration
1.5 Architectural Organization
1.6 Organization of the Book
Bibliography
Chapter 2 The Internet
2.1 Origin and Organization
2.1.1 ISPs and the Topology of the Internet
2.2 Addressing the Nodes
2.3 Network Connection Protocol
2.3.1 IP Protocol
2.3.2 Transmission Control Protocol
2.3.3 User Datagram Protocol
2.4 Dynamic Host Control Protocol
2.5 Domain Name Service
2.5.1 Reverse DNS Lookup
2.5.2 Client Server Architecture
2.6 Content Distribution Network
2.7 Conclusion
Exercises
Bibliography
Chapter 3 Process to Process Communication
3.1 Communication Types and Interfaces
3.1.1 Sequential Type
3.1.2 Declarative Type
3.1.3 Shared States
3.1.4 Message Passing
3.1.5 Communication Interfaces
3.2 Socket Programming
3.2.1 Socket Data Structures
3.2.2 Socket Calls
3.3 Remote Procedure Call
3.3.1 XML RPC
3.4 Remote Method Invocation
3.5 Conclusion
Exercises
Additional Web Resources
Bibliography
Chapter 4 Microservices, Containerization, and MPI
4.1 Microservice Architecture
4.2 REST Requests and APIs
4.2.1 Weather Data Using REST API
4.3 Cross Platform Applications
4.4 Message Passing Interface
4.4.1 Process Communication Models
4.4.2 Programming with MPI
4.5 Conclusion
Exercises
Additional Internet Resources
Bibliography
Chapter 5 Clock Synchronization and Event Ordering
5.1 The Notion of Clock Time
5.2 External Clock Based Mechanisms
5.2.1 Cristian's Algorithm
5.2.2 Berkeley Clock Protocol
5.2.3 Network Time Protocol
5.2.3.1 Symmetric Mode of Operation
5.3 Events and Temporal Ordering
5.3.1 Causal Dependency
5.4 Logical Clock
5.5 Causal Ordering of Messages
5.6 Multicast Message Ordering
5.6.1 Implementing FIFO Multicast
5.6.2 Implementing Causal Ordering
5.6.3 Implementing Total Ordering
5.6.4 Reliable Multicast
5.7 Interval Events
5.7.1 Conceptual Neighborhood
5.7.2 Spatial Events
5.8 Conclusion
Exercises
Bibliography
Chapter 6 Global States and Termination Detection
6.1 Cuts and Global States
6.1.1 Global States
6.1.2 Recording of Global States
6.1.3 Problem in Recording Global State
6.2 Liveness and Safety
6.3 Termination Detection
6.3.1 Snapshot Based Termination Detection
6.3.2 Ring Method
6.3.3 Tree Method
6.3.4 Weight Throwing Method
6.4 Conclusion
Exercises
Bibliography
Chapter 7 Leader Election
7.1 Impossibility Result
7.2 Bully Algorithm
7.3 Ring‐Based Algorithms
7.3.1 Circulate IDs All the Way
7.3.2 As Far as an ID Can Go
7.4 Hirschberg and Sinclair Algorithm
7.5 Distributed Spanning Tree Algorithm
7.5.1 Single Initiator Spanning Tree
7.5.2 Multiple Initiators Spanning Tree
7.5.3 Minimum Spanning Tree
7.6 Leader Election in Trees
7.6.1 Overview of the Algorithm
7.6.2 Activation Stage
7.6.3 Saturation Stage
7.6.4 Resolution Stage
7.6.5 Two Nodes Enter SATURATED State
7.7 Leased Leader Election
7.8 Conclusion
Exercises
Bibliography
Chapter 8 Mutual Exclusion
8.1 System Model
8.2 Coordinator‐Based Solution
8.3 Assertion‐Based Solutions
8.3.1 Lamport's Algorithm
8.3.2 Improvement to Lamport's Algorithm
8.3.3 Quorum‐Based Algorithms
8.4 Token‐Based Solutions
8.4.1 Suzuki and Kasami's Algorithm
8.4.2 Singhal's Heuristically Aided Algorithm
8.4.3 Raymond's Tree‐Based Algorithm
8.5 Conclusion
Exercises
Bibliography
Chapter 9 Agreements and Consensus
9.1 System Model
9.1.1 Failures in Distributed System
9.1.2 Problem Definition
9.1.3 Agreement Problem and Its Equivalence
9.2 Byzantine General Problem (BGP)
9.2.1 BGP Solution Using Oral Messages
9.2.2 Phase King Algorithm
9.3 Commit Protocols
9.3.1 Two‐Phase Commit Protocol
9.3.2 Three‐Phase Commit
9.4 Consensus
9.4.1 Consensus in Synchronous Systems
9.4.2 Consensus in Asynchronous Systems
9.4.3 Paxos Algorithm
9.4.4 Raft Algorithm
9.4.5 Leader Election
9.5 Conclusion
Exercises
Bibliography
Chapter 10 Gossip Protocols
10.1 Direct Mail
10.2 Generic Gossip Protocol
10.3 Anti‐entropy
10.3.1 Push‐Based Anti‐Entropy
10.3.2 Pull‐Based Anti‐Entropy
10.3.3 Hybrid Anti‐Entropy
10.3.4 Control and Propagation in Anti‐Entropy
10.4 Rumor‐mongering Gossip
10.4.1 Analysis of Rumor Mongering
10.4.2 Fault‐Tolerance
10.5 Implementation Issues
10.5.1 Network‐Related Issues
10.6 Applications of Gossip
10.6.1 Peer Sampling
10.6.2 Failure Detectors
10.6.3 Distributed Social Networking
10.7 Gossip in IoT Communication
10.7.1 Context‐Aware Gossip
10.7.2 Flow‐Aware Gossip
10.7.2.1 Fire Fly Gossip
10.7.2.2 Trickle
10.8 Conclusion
Exercises
Bibliography
Chapter 11 Message Diffusion Using Publish and Subscribe
11.1 Publish and Subscribe Paradigm
11.1.1 Broker Network
11.2 Filters and Notifications
11.2.1 Subscription and Advertisement
11.2.2 Covering Relation
11.2.3 Merging Filters
11.2.4 Algorithms
11.3 Notification Service
11.3.1 Siena
11.3.2 Rebeca
11.3.3 Routing of Notification
11.4 MQTT
11.5 Advanced Message Queuing Protocol
11.6 Effects of Technology on Performance
11.7 Conclusions
Exercises
Bibliography
Chapter 12 Peer‐to‐Peer Systems
12.1 The Origin and the Definition of P2P
12.2 P2P Models
12.2.1 Routing in P2P Network
12.3 Chord Overlay
12.4 Pastry
12.5 CAN
12.6 Kademlia
12.7 Conclusion
Exercises
Bibliography
Chapter 13 Distributed Shared Memory
13.1 Multicore and S‐DSM
13.1.1 Coherency by Delegation to a Central Server
13.2 Manycore Systems and S‐DSM
13.3 Programming Abstractions
13.3.1 MapReduce
13.3.2 OpenMP
13.3.3 Merging Publish and Subscribe with DSM
13.4 Memory Consistency Models
13.4.1 Sequential Consistency
13.4.2 Linearizability or Atomic Consistency
13.4.3 Relaxed Consistency Models
13.4.3.1 Release Consistency
13.4.4 Comparison of Memory Models
13.5 DSM Access Algorithms
13.5.1 Central Sever Algorithm
13.5.2 Migration Algorithm
13.5.3 Read Replication Algorithm
13.5.4 Full Replication Algorithm
13.6 Conclusion
Exercises
Bibliography
Chapter 14 Distributed Data Management
14.1 Distributed Storage Systems
14.1.1 RAID
14.1.2 Storage Area Networks
14.1.3 Cloud Storage
14.2 Distributed File Systems
14.3 Distributed Index
14.4 NoSQL Databases
14.4.1 Key‐Value and Document Databases
14.4.1.1 MapReduce Algorithm
14.4.2 Wide Column Databases
14.4.3 Graph Databases
14.4.3.1 Pregel Algorithm
14.5 Distributed Data Analytics
14.5.1 Distributed Clustering Algorithms
14.5.1.1 Distributed K‐Means Clustering Algorithm
14.5.2 Stream Clustering
14.5.2.1 BIRCH Algorithm
14.6 Conclusion
Exercises
Bibliography
Chapter 15 Distributed Knowledge Management
15.1 Distributed Knowledge
15.2 Distributed Knowledge Representation
15.2.1 Resource Description Framework (RDF)
15.2.2 Web Ontology Language (OWL)
15.3 Linked Data
15.3.1 Friend of a Friend
15.3.2 DBpedia
15.4 Querying Distributed Knowledge
15.4.1 SPARQL Query Language
15.4.2 SPARQL Query Semantics
15.4.3 SPARQL Query Processing
15.4.4 Distributed SPARQL Query Processing
15.4.5 Federated and Peer‐to‐Peer SPARQL Query Processing
15.5 Data Integration in Distributed Sensor Networks
15.5.1 Semantic Data Integration
15.5.2 Data Integration in Constrained Systems
15.6 Conclusion
Exercises
Bibliography
Chapter 16 Distributed Intelligence
16.1 Agents and Multi‐Agent Systems
16.1.1 Agent Embodiment
16.1.2 Mobile Agents
16.1.3 Multi‐Agent Systems
16.2 Communication in Agent‐Based Systems
16.2.1 Agent Communication Protocols
16.2.2 Interaction Protocols
16.2.2.1 Request Interaction Protocol
16.3 Agent Middleware
16.3.1 FIPA Reference Model
16.3.2 FIPA Compliant Middleware
16.3.2.1 JADE: Java Agent Development Environment
16.3.2.2 MobileC
16.3.3 Agent Migration
16.4 Agent Coordination
16.4.1 Planning
16.4.1.1 Distributed Planning Paradigms
16.4.1.2 Distributed Plan Representation and Execution
16.4.2 Task Allocation
16.4.2.1 Contract‐Net Protocol
16.4.2.2 Allocation of Multiple Tasks
16.4.3 Coordinating Through the Environment
16.4.3.1 Construct‐Ant‐Solution
16.4.3.2 Update‐Pheromone
16.4.4 Coordination Without Communication
16.5 Conclusion
Exercises
Bibliography
Chapter 17 Distributed Ledger
17.1 Cryptographic Techniques
17.2 Distributed Ledger Systems
17.2.1 Properties of Distributed Ledger Systems
17.2.2 A Framework for Distributed Ledger Systems
17.3 Blockchain
17.3.1 Distributed Consensus in Blockchain
17.3.2 Forking
17.3.3 Distributed Asset Tracking
17.3.4 Byzantine Fault Tolerance and Proof of Work
17.4 Other Techniques for Distributed Consensus
17.4.1 Alternative Proofs
17.4.2 Non‐linear Data Structures
17.4.2.1 Tangle
17.4.2.2 Hashgraph
17.5 Scripts and Smart Contracts
17.6 Distributed Ledgers for Cyber‐Physical Systems
17.6.1 Layered Architecture
17.6.2 Smart Contract in Cyber‐Physical Systems
17.7 Conclusion
Exercises
Bibliography
Chapter 18 Case Study
18.1 Collaborative E‐Learning Systems
18.2 P2P E‐Learning System
18.2.1 Web Conferencing Versus P2P‐IPS
18.3 P2P Shared Whiteboard
18.3.1 Repainting Shared Whiteboard
18.3.2 Consistency of Board View at Peers
18.4 P2P Live Streaming
18.4.1 Peer Joining
18.4.2 Peer Leaving
18.4.3 Handling “Ask Doubt”
18.5 P2P‐IPS for Stored Contents
18.5.1 De Bruijn Graphs for DHT Implementation
18.5.2 Node Information Structure
18.5.2.1 Join Example
18.5.3 Leaving of Peers
18.6 Searching, Sharing, and Indexing
18.6.1 Pre‐processing of Files
18.6.2 File Indexing
18.6.3 File Lookup and Download
18.7 Annotations and Discussion Forum
18.7.1 Annotation Format
18.7.2 Storing Annotations
18.7.3 Audio and Video Annotation
18.7.4 PDF Annotation
18.7.5 Posts, Comments, and Announcements
18.7.6 Synchronization of Posts and Comments
18.7.6.1 Epidemic Dissemination
18.7.6.2 Reconciliation
18.8 Simulation Results
18.8.1 Live Streaming and Shared Whiteboard
18.8.2 De Bruijn Overlay
18.9 Conclusion
Bibliography
Index
EULA