book

Distributed Systems, 2nd Edition

Name: Distributed Systems, 2nd Edition
Author: Sukumar Ghosh
ISBN: 9781498760058

by Sukumar Ghosh

July 2014

Intermediate to advanced

554 pages

17h 49m

English

Chapman and Hall/CRC

Read now

Unlock full access

Preface
Acknowledgments
Author
Section I - Background Materials
Chapter 1 - Introduction
1.1 What Is a Distributed System?1.2 Why Distributed Systems1.3 Examples of Distributed Systems1.4 Important Issues in Distributed Systems1.5 Common Subproblems1.6 Implementing a Distributed System1.7 Parallel versus Distributed Systems1.8 Bibliographic NotesExercises
Chapter 2 - Interprocess Communication: An Overview
2.1 Introduction2.1.1 Processes and Threads2.1.2 Client–Server Model2.1.3 Middleware2.2 Network Protocols2.2.1 Ethernet2.2.2 Wireless Networks2.2.3 OSI Model2.2.4 IP2.2.5 Transport Layer Protocols2.2.6 Interprocess Communication Using Sockets2.3 Naming2.3.1 Domain Name Service2.3.2 Naming Service for Mobile Clients2.4 Remote Procedure Call2.4.1 Implementing RPC2.4.2 Sun ONC/RPC2.5 Remote Method Invocation2.6 Messages2.6.1 Transient and Persistent Messages2.6.2 Streams2.7 Web Services2.8 Event Notification2.9 Virtualization: Cloud Computing2.9.1 Classification of Cloud Services2.9.2 MapReduce2.9.3 Hadoop2.10 Mobile Agents2.11 Basic Group Communication Services2.12 Concluding Remarks2.13 Bibliographic NotesExercises
Section II - Foundational Topics
Chapter 3 - Models for Communication
3.1 Need for a Model3.2 Message-Passing Model for Interprocess Communication3.2.1 Process Actions3.2.2 Channels3.2.3 Synchronous versus Asynchronous Systems3.2.4 Real-Time Systems3.3 Shared Variables3.3.1 Linda3.4 Modeling Mobile Agents3.5 Relationship among Models3.5.1 Strong and Weak Models3.5.2 Implementing a FIFO Channel Using a Non-FIFO Channel3.5.3 Implementing Message Passing Using Shared Memory3.5.4 Implementing Shared Memory Using Message Passing3.5.5 Impossibility Result with Channels3.6 Classification Based on Special Properties3.6.1 Reactive versus Transformational Systems3.6.2 Named versus Anonymous Systems3.7 Complexity Measures3.8 Concluding Remarks3.9 Bibliographic NotesExercises
Chapter 4 - Representing Distributed Algorithms: Syntax and Semantics
4.1 Introduction4.2 Guarded Actions4.3 Nondeterminism4.4 Atomic Operations4.5 Fairness4.6 Central versus Distributed Schedulers4.7 Concluding Remarks4.8 Bibliographic NotesExercises
Chapter 5 - Program Correctness
5.1 Introduction5.2 Correctness Criteria5.2.1 Safety Properties5.2.2 Liveness Properties5.3 Correctness Proofs5.3.1 Quick Review of Propositional Logic5.3.2 Brief Overview of Predicate Logic5.4 Assertional Reasoning: Proving Safety Properties5.5 Proving Liveness Properties Using Well-Founded Sets5.6 Programming Logic5.7 Predicate Transformers5.8 Concluding Remarks5.9 Bibliographic NotesExercises

Chapter 6 - Time in a Distributed System
6.1 Introduction6.1.1 Physical Time6.1.2 Sequential and Concurrent Events6.2 Logical Clocks6.3 Vector Clocks6.4 Physical Clock Synchronization6.4.1 Preliminary Definitions6.4.2 Clock Reading Error6.4.3 Algorithms for Internal Synchronization6.4.4 Algorithms for External Synchronization6.5 Concluding Remarks6.6 Bibliographic NotesExercises
Section III - Important Paradigms
Chapter 7 - Mutual Exclusion
7.1 Introduction7.2 Solutions on Message-Passing Systems7.2.1 Lamport’s Solution7.2.2 Ricart–Agrawala’s Solution7.2.3 Maekawa’s Solution7.3 Token-Passing Algorithms7.3.1 Suzuki–Kasami Algorithm7.3.2 Raymond’s Algorithm7.4 Solutions on the Shared-Memory Model7.4.1 Peterson’s Algorithm7.5 Mutual Exclusion Using Special Instructions7.5.1 Solution Using Test-and-Set7.5.2 Solution Using Load-Linked and Store-Conditional7.6 Group Mutual Exclusion7.7 Concluding Remarks7.8 Bibliographic NotesExercises
Chapter 8 - Distributed Snapshot
8.1 Introduction8.2 Properties of Consistent Snapshots8.2.1 Cuts and Consistent Cuts8.3 Chandy–Lamport Algorithm8.3.1 Two Examples8.3.1.1 Example 1: Counting of Tokens8.3.1.2 Example 2: Communicating State Machines8.4 Lai–Yang Algorithm8.5 Distributed Debugging8.5.1 Constructing the State Lattice8.5.2 Evaluating Predicates8.6 Concluding Remarks8.7 Bibliographic NotesExercises
Chapter 9 - Global State Collection
9.1 Introduction9.2 Elementary Algorithm for All-to-All Broadcasting9.3 Termination-Detection Algorithms9.3.1 Dijkstra–Scholten Algorithm9.3.2 Termination Detection on a Unidirectional Ring9.3.3 Credit-Recovery Algorithm for Termination Detection9.4 Wave Algorithms9.4.1 Propagation of Information with Feedback9.5 Distributed Deadlock Detection9.5.1 Resource Deadlock and Communication Deadlock9.5.2 Detection of Resource Deadlock9.5.3 Detection of Communication Deadlock9.6 Concluding Remarks9.7 Bibliographic NotesExercises
Chapter 10 - Graph Algorithms
10.1 Introduction10.2 Routing Algorithms10.2.1 Computation of Shortest Path10.2.1.1 Complexity Analysis10.2.1.2 Chandy–Misra Modification of the Shortest Path Algorithm10.2.2 Distance-Vector Routing10.2.3 Link-State Routing10.2.4 Interval Routing10.2.4.1 Interval Routing Rule10.2.5 Prefix Routing10.3 Graph Traversal10.3.1 Spanning Tree Construction10.3.2 Tarry’s Graph Traversal Algorithm10.3.3 Minimum Spanning Tree Construction10.3.3.1 Overall Strategy10.3.3.2 Detecting the Least Weight Outgoing Edge10.3.3.3 Message Complexity10.4 Graph Coloring10.4.1 (D + 1)-Coloring Algorithm10.4.2 6-Coloring of Planar Graphs10.5 Cole–Vishkin Reduction Algorithm for Tree Coloring10.6 Maximal Independent Set: Luby’s Algorithm10.7 Concluding Remarks10.8 Bibliographic NotesExercises
Chapter 11 - Coordination Algorithms
11.1 Introduction11.2 Leader Election11.2.1 Bully Algorithm11.2.2 Maxima Finding on a Ring11.2.2.1 Chang–Roberts Algorithm11.2.2.2 Franklin’s Algorithm11.2.2.3 Peterson’s Algorithm11.2.3 Election in Arbitrary Networks11.2.4 Election in Anonymous Networks11.3 Synchronizers11.3.1 ABD Synchronizer11.3.2 Awerbuch’s Synchronizers11.3.2.1 α-Synchronizer11.3.2.2 β-Synchronizer11.3.2.3 γ-Synchronizer11.3.2.4 Performance of Synchronizer-Based Algorithms11.4 Concluding Remarks11.5 Bibliographic NotesExercises
Section IV - Faults and Fault-Tolerant Systems
Chapter 12 - Fault-Tolerant Systems
12.1 Introduction12.2 Classification of Faults12.3 Specification of Faults12.4 Fault-Tolerant Systems12.4.1 Masking Tolerance12.4.2 Nonmasking Tolerance12.4.3 Fail-Safe Tolerance12.4.4 Graceful Degradation12.4.5 Detection of Failures in Synchronous Systems12.5 Tolerating Crash Failures12.5.1 Double and Triple Modular Redundancy12.6 Tolerating Omission Failures12.6.1 Stenning’s Protocol12.6.2 Sliding Window Protocol12.6.3 Alternating Bit Protocol12.6.4 How TCP Works12.7 Concluding Remarks12.8 Bibliographic NotesExercises
Chapter 13 - Distributed Consensus
13.1 Introduction13.2 Consensus in Asynchronous Systems13.2.1 Bivalent and Univalent States13.3 Consensus in Synchronous Systems: Byzantine Generals Problem13.3.1 Solution with No Traitor13.3.2 Solution with Traitors: Interactive Consistency Criteria13.3.3 Consensus with Oral Messages13.3.3.1 Impossibility Result13.3.3.2 OM(m) Algorithm13.3.4 Consensus Using Signed Messages13.4 Paxos Algorithm13.4.1 Safety Properties13.4.2 Liveness Properties13.5 Failure Detectors13.5.1 Solving Consensus Using Failure Detectors13.5.1.1 Consensus Using P13.5.1.2 Consensus Using S13.5.1.3 Rationale13.5.1.4 Implementing a Failure Detector13.6 Concluding Remarks13.7 Bibliographic NotesExercises
Chapter 14 - Distributed Transactions
14.1 Introduction14.2 Classification of Transactions14.2.1 Flat Transactions14.2.2 Nested Transactions14.2.3 Distributed Transactions14.3 Implementing Transactions14.4 Concurrency Control and Serializability14.4.1 Testing for Serializability14.4.2 Two-Phase Locking14.4.3 Concurrency Control via Time Stamp Ordering14.5 Atomic Commit Protocols14.5.1 One-Phase Commit14.5.2 Two-Phase Commit14.5.3 Three-Phase Commit14.6 Recovery from Failures14.6.1 Stable Storage14.6.2 Checkpointing and Rollback Recovery14.6.3 Message Logging14.7 Concluding Remarks14.8 Bibliographic NotesExercises
Chapter 15 - Group Communication
15.1 Introduction15.2 Atomic Multicast15.3 IP Multicast15.3.1 Reverse Path Forwarding15.4 Application Layer Multicast15.5 Ordered Multicasts15.5.1 Implementing Total Order Multicast15.5.1.1 Implementation Using a Sequencer15.5.1.2 Distributed Implementation15.5.2 Implementing Causal Order Multicast15.6 Reliable Multicast15.6.1 Scalable Reliable Multicast15.6.2 Reliable Ordered Multicast15.7 Open Groups15.7.1 View-Synchronous Group Communication15.8 Overview of Transis15.9 Concluding Remarks15.10 Bibliographic NotesExercises
Chapter 16 - Replicated Data Management
16.1 Introduction16.1.1 Reliability versus Availability16.2 Architecture of Replicated Data Management16.2.1 Passive versus Active Replication16.2.2 Fault-Tolerant State Machines16.3 Data-Centric Consistency Models16.3.1 Strict Consistency16.3.2 Linearizability16.3.3 Sequential Consistency16.3.4 Causal Consistency16.3.5 FIFO Consistency16.4 Client-Centric Consistency Protocols16.4.1 Eventual Consistency16.4.2 Consistency Models for Mobile Clients16.4.2.1 Read-After-Read Consistency16.4.2.2 Write-After-Write Consistency16.4.2.3 Read-After-Write Consistency16.4.2.4 Write-After-Read Consistency16.5 Implementation of Data-Centric Consistency Models16.6 Quorum-Based Protocols16.7 Replica Placement16.8 Brewer’s CAP Theorem16.9 Case Studies16.9.1 Replication Management in Coda16.9.2 Replication Management in Bayou16.9.3 Amazon Dynamo16.10 Concluding Remarks16.11 Bibliographic NotesExercises
Chapter 17 - Self-Stabilizing Systems
17.1 Introduction17.2 Theoretical Foundations17.3 Stabilizing Mutual Exclusion17.3.1 Mutual Exclusion on a Unidirectional Ring17.3.2 Mutual Exclusion on a Bidirectional Array17.4 Stabilizing Graph Coloring17.5 Stabilizing Spanning Tree Protocol17.6 Stabilizing Maximal Matching17.7 Distributed Reset17.8 Stabilizing Clock Phase Synchronization17.9 Concluding Remarks17.10 Bibliographic NotesExercises
Section V - Real-World Issues
Chapter 18 - Distributed Discrete-Event Simulation
18.1 Introduction18.1.1 Event-Driven Simulation18.2 Distributed Simulation18.2.1 Challenges18.2.2 Correctness Issues18.3 Conservative Simulation18.4 Optimistic Simulation and Time Warp18.4.1 Global Virtual Time18.5 Concluding Remarks18.6 Bibliographic NotesExercises
Chapter 19 - Security in Distributed Systems
19.1 Introduction19.2 Security Mechanisms19.3 Common Security Attacks19.3.1 Eavesdropping19.3.2 Denial of Service19.3.3 Data Tampering19.3.4 Masquerading19.3.5 Man in the Middle19.3.6 Malicious Software19.3.6.1 Virus19.3.6.2 Worms19.3.6.3 Spyware19.4 Encryption19.5 Secret Key Cryptosystem19.5.1 Confusion and Diffusion19.5.2 DES19.5.3 3DES19.5.4 AES19.5.5 One-Time Pad19.5.6 Stream Ciphers19.5.7 Steganography19.6 Public Key Cryptosystems19.6.1 Rivest–Shamir–Adleman Cryptosystem19.6.2 ElGamal Cryptosystem19.7 Digital Signatures19.7.1 Signatures in Secret-Key Cryptosystems19.7.2 Signatures in Public-Key Cryptosystems19.8 Hashing Algorithms19.8.1 Birthday Attack19.9 Elliptic Curve Cryptography19.10 Authentication Server19.10.1 Authentication Service for Secret-Key Cryptosystems19.10.2 Authentication Server for Public-Key Systems19.11 Digital Certificates19.12 Case Studies19.12.1 Kerberos19.12.2 Pretty Good Privacy19.12.3 Secure Socket Layer19.13 Virtual Private Networks and Firewalls19.13.1 Virtual Private Network19.13.2 Firewall19.14 Sharing a Secret19.15 Concluding Remarks19.16 Bibliographic NotesExercisesProgramming Exercises
Chapter 20 - Sensor Networks
20.1 Vision20.2 Architecture of Sensor Nodes20.2.1 MICA Mote20.2.2 ZigBee-Enabled Sensor Nodes20.2.3 TinyOS® Operating System20.3 Challenges in Wireless Sensor Networks20.3.1 Energy Conservation20.3.2 Fault Tolerance20.3.3 Routing20.3.4 Time Synchronization20.3.5 Location Management20.3.6 Middleware Design20.3.7 Security20.4 Routing Algorithms20.4.1 Directed Diffusion20.4.2 Cluster-Based Routing20.4.2.1 LEACH20.4.2.2 PEGASIS20.4.3 Metadata-Based Routing: SPIN20.5 Time Synchronization Using Reference Broadcast20.5.1 Reference Broadcast20.6 Localization Algorithms20.6.1 RSSI-Based Ranging20.6.2 Ranging Using Time Difference of Arrival20.6.3 Anchor-Based Ranging20.7 Security in Sensor Networks20.7.1 SPIN for Data Security20.7.1.1 Overview of SNEP20.7.1.2 Overview of μTESLA20.7.2 Attacks on Routing20.7.2.1 Hello Flood20.8 Applications20.8.1 Health-Care Applications20.8.2 Environment Monitoring and Control20.8.3 Citizen Sensing20.8.4 Pursuer–Evader Game20.9 Concluding Remarks20.10 Bibliographic NotesExercisesProgramming Exercises
Chapter 21 - Social and Peer-to-Peer Networks
21.1 Introduction to Social Networks21.1.1 Milgram’s Experiment21.2 Metrics of Social Networks21.2.1 Clustering Coefficient21.2.2 Diameter21.3 Modeling Social Networks21.3.1 Erdös–Rényi Model21.3.2 Small-World Model21.3.3 Power-Law Graphs21.4 Centrality Measures in Social Networks21.4.1 Degree Centrality21.4.2 Closeness Centrality21.4.3 Betweenness Centrality21.5 Community Detection21.5.1 Girvan–Newman Algorithm21.6 Introduction to Peer-to-Peer Networks21.7 First-Generation P2P Systems21.7.1 Napster21.7.2 Gnutella21.8 Second-Generation P2P Systems21.8.1 KaZaA21.8.2 Chord21.8.3 Content-Addressable Network21.8.4 Pastry21.9 Koorde and De Bruijn Graph21.10 Skip Graph21.11 Replication Management21.12 BitTorrent and Free Riding21.13 Censorship Resistance, Anonymity21.14 Concluding Remarks21.15 Bibliographic NotesExercises
References

Content preview from Distributed Systems, 2nd Edition

Chapter 11

Coordination Algorithms

11.1 Introduction

Distributed applications rely on specific forms of coordination among processes to accomplish their goals. Some tasks of coordination can be viewed as a form of preprocessing. Examples include clock synchronization, spanning tree construction, and leader election. In this section, we single out a couple of specific coordination algorithms and explain their construction. Our first example addresses leader election, where one among a designated set of processes is chosen as leader and assigned special responsibilities. The second example addresses a problem of model transformation: Recall that asynchrony is hard to deal with in real-life applications due to the lack of temporal guarantees—it ...

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.

Read now

Unlock full access

More than 5,000 organizations count on O’Reilly

O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.

Julian F.

Head of Cybersecurity

I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.

Addison B.

Field Engineer

I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.

Amir M.

Data Platform Tech Lead

I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.

Mark W.

Embedded Software Engineer

Publisher Resources

ISBN: 9781466552975

Cloud Computing

Data Engineering

Data Science

AI & ML

Programming Languages

Software Architecture

IT/Ops

Security

Design

Business

Soft Skills

Distributed Systems, 2nd Edition

by Sukumar Ghosh

Coordination Algorithms

11.1 Introduction

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.