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