Distributed Systems: An Algorithmic Approach, Second Edition, 2nd Edition (Hardback) book cover

Distributed Systems

An Algorithmic Approach, Second Edition, 2nd Edition

By Sukumar Ghosh

Chapman and Hall/CRC

554 pages | 184 B/W Illus.

Purchasing Options:$ = USD
Hardback: 9781466552975
pub: 2014-07-14
SAVE ~$21.00
$140.00
$119.00
x
eBook (VitalSource) : 9780429192357
pub: 2014-07-14
from $28.98


FREE Standard Shipping!

Description

Distributed Systems: An Algorithmic Approach, Second Edition provides a balanced and straightforward treatment of the underlying theory and practical applications of distributed computing. As in the previous version, the language is kept as unobscured as possible—clarity is given priority over mathematical formalism. This easily digestible text:

  • Features significant updates that mirror the phenomenal growth of distributed systems
  • Explores new topics related to peer-to-peer and social networks
  • Includes fresh exercises, examples, and case studies

Supplying a solid understanding of the key principles of distributed computing and their relationship to real-world applications, Distributed Systems: An Algorithmic Approach, Second Edition makes both an ideal textbook and a handy professional reference.

Reviews

"… a welcome and very detailed collection of almost everything ‘distributed.’ … The breadth of concepts discussed is extensive and backed up with examples and detailed student exercises, making this an excellent reference and textbook. … In all, the book—with its depth and breadth of information on relevant technologies involved in all phases of complex distributed programming—is an excellent addition to the published works on some of the 21st century’s hardest computing problems."

Computing Reviews, March 2015

"This text presents the material in a clear and straightforward manner, making it accessible to undergraduate students while still maintaining value for experts. The book contains material for both researchers and practitioners, and the new version adds even more relevant and cutting-edge topics in the field while continuing the excellent coverage of the fundamentals. The second version is a natural addition to the bookshelves of anyone interested in distributed algorithms."

—Andrew Berns, University of Wisconsin-La Crosse, USA

"The main theme of this edition, as in the first edition, is to show the implementation of distributed algorithms as well as to describe the rich theory behind them. [The second edition] is well organized and shows the implementation details of distributed algorithms without sacrificing the theory. The contents are enriched by the addition of new chapters. This book is essential reading for senior/graduate classes on distributed systems and algorithms. I strongly recommend it."

—Kayhan Erciyes, Izmir University, Turkey

Table of Contents

Preface

Acknowledgments

Author

Section I: Background Materials

Introduction

What Is a Distributed System?

Why Distributed Systems

Examples of Distributed Systems

Important Issues in Distributed Systems

Common Subproblems

Implementing a Distributed System

Parallel versus Distributed Systems

Bibliographic Notes

Exercises

Interprocess Communication: An Overview

Introduction

Processes and Threads

Client–Server Model

Middleware

Network Protocols

Ethernet

Wireless Networks

OSI Model

IP

Transport Layer Protocols

Interprocess Communication Using Sockets

Naming

Domain Name Service

Naming Service for Mobile Clients

Remote Procedure Call

Implementing RPC

Sun ONC/RPC

Remote Method Invocation

Messages

Transient and Persistent Messages

Streams

Web Services

Event Notification

Virtualization: Cloud Computing

Classification of Cloud Services

MapReduce

Hadoop

Mobile Agents

Basic Group Communication Services

Concluding Remarks

Bibliographic Notes

Exercises

Section II: Foundational Topics

Models for Communication

Need for a Model

Message-Passing Model for Interprocess Communication

Process Actions

Channels

Synchronous versus Asynchronous Systems

Real-Time Systems

Shared Variables

Linda

Modeling Mobile Agents

Relationship among Models

Strong and Weak Models

Implementing a FIFO Channel Using a Non-FIFO Channel

Implementing Message Passing Using Shared Memory

Implementing Shared Memory Using Message Passing

Impossibility Result with Channels

Classification Based on Special Properties

Reactive versus Transformational Systems

Named versus Anonymous Systems

Complexity Measures

Concluding Remarks

Bibliographic Notes

Exercises

Representing Distributed Algorithms: Syntax and Semantics

Introduction

Guarded Actions

Nondeterminism

Atomic Operations

Fairness

Central versus Distributed Schedulers

Concluding Remarks

Bibliographic Notes

Exercises

Program Correctness

Introduction

Correctness Criteria

Safety Properties

Liveness Properties

Correctness Proofs

Quick Review of Propositional Logic

Brief Overview of Predicate Logic

Assertional Reasoning: Proving Safety Properties

Proving Liveness Properties Using Well-Founded Sets

Programming Logic

Predicate Transformers

Concluding Remarks

Bibliographic Notes

Exercises

Time in a Distributed System

Introduction

Physical Time

Sequential and Concurrent Events

Logical Clocks

Vector Clocks

Physical Clock Synchronization

Preliminary Definitions

Clock Reading Error

Algorithms for Internal Synchronization

Algorithms for External Synchronization

Concluding Remarks

Bibliographic Notes

Exercises

Section III: Important Paradigms

Mutual Exclusion

Introduction

Solutions on Message-Passing Systems

Lamport’s Solution

Ricart–Agrawala’s Solution

Maekawa’s Solution

Token-Passing Algorithms

Suzuki–Kasami Algorithm

Raymond’s Algorithm

Solutions on the Shared-Memory Model

Peterson’s Algorithm

Mutual Exclusion Using Special Instructions

Solution Using Test-and-Set

Solution Using Load-Linked and Store-Conditional

Group Mutual Exclusion

Concluding Remarks

Bibliographic Notes

Exercises

Distributed Snapshot

Introduction

Properties of Consistent Snapshots

Cuts and Consistent Cuts

Chandy–Lamport Algorithm

Two Examples

Lai–Yang Algorithm

Distributed Debugging

Constructing the State Lattice

Evaluating Predicates

Concluding Remarks

Bibliographic Notes

Exercises

Global State Collection

Introduction

Elementary Algorithm for All-to-All Broadcasting

Termination-Detection Algorithms

Dijkstra–Scholten Algorithm

Termination Detection on a Unidirectional Ring

Credit-Recovery Algorithm for Termination Detection

Wave Algorithms

Propagation of Information with Feedback

Distributed Deadlock Detection

Resource Deadlock and Communication Deadlock

Detection of Resource Deadlock

Detection of Communication Deadlock

Concluding Remarks

Bibliographic Notes

Exercises

Graph Algorithms

Introduction

Routing Algorithms

Computation of Shortest Path

Distance-Vector Routing

Link-State Routing

Interval Routing

Prefix Routing

Graph Traversal

Spanning Tree Construction

Tarry’s Graph Traversal Algorithm

Minimum Spanning Tree Construction

Graph Coloring

(D + 1)-Coloring Algorithm

Cole–Vishkin Reduction Algorithm for Tree Coloring

Maximal Independent Set: Luby’s Algorithm

Concluding Remarks

Bibliographic Notes

Exercises

Coordination Algorithms

Introduction

Leader Election

Bully Algorithm

Maxima Finding on a Ring

Election in Arbitrary Networks

Election in Anonymous Networks

Synchronizers

ABD Synchronizer

Awerbuch’s Synchronizers

Concluding Remarks

Bibliographic Notes

Exercises

Section IV: Faults and Fault-Tolerant Systems

Fault-Tolerant Systems

Introduction

Classification of Faults

Specification of Faults

Fault-Tolerant Systems

Masking Tolerance

Nonmasking Tolerance

Fail-Safe Tolerance

Graceful Degradation

Detection of Failures in Synchronous Systems

Tolerating Crash Failures

Double and Triple Modular Redundancy

Tolerating Omission Failures

Stenning’s Protocol

Sliding Window Protocol

Alternating Bit Protocol

How TCP Works

Concluding Remarks

Bibliographic Notes

Exercises

Distributed Consensus

Introduction

Consensus in Asynchronous Systems

Bivalent and Univalent States

Consensus in Synchronous Systems: Byzantine Generals Problem

Solution with No Traitor

Solution with Traitors: Interactive Consistency Criteria

Consensus with Oral Messages

Consensus Using Signed Messages

Paxos Algorithm

Safety Properties

Liveness Properties

Failure Detectors

Solving Consensus Using Failure Detectors

Concluding Remarks

Bibliographic Notes

Exercises

Distributed Transactions

Introduction

Classification of Transactions

Flat Transactions

Nested Transactions

Distributed Transactions

Implementing Transactions

Concurrency Control and Serializability

Testing for Serializability

Two-Phase Locking

Concurrency Control via Time Stamp Ordering

Atomic Commit Protocols

One-Phase Commit

Two-Phase Commit

Three-Phase Commit

Recovery from Failures

Stable Storage

Checkpointing and Rollback Recovery

Message Logging

Concluding Remarks

Bibliographic Notes

Exercises

Group Communication

Introduction

Atomic Multicast

IP Multicast

Reverse Path Forwarding

Application Layer Multicast

Ordered Multicasts

Implementing Total Order Multicast

Implementing Causal Order Multicast

Reliable Multicast

Scalable Reliable Multicast

Reliable Ordered Multicast

Open Groups

View-Synchronous Group Communication

Overview of Transis

Concluding Remarks

Bibliographic Notes

Exercises

Replicated Data Management

Introduction

Reliability versus Availability

Architecture of Replicated Data Management

Passive versus Active Replication

Fault-Tolerant State Machines

Data-Centric Consistency Models

Strict Consistency

Linearizability

Sequential Consistency

Causal Consistency

FIFO Consistency

Client-Centric Consistency Protocols

Eventual Consistency

Consistency Models for Mobile Clients

Implementation of Data-Centric Consistency Models

Quorum-Based Protocols

Replica Placement

Brewer’s CA P Theorem

Case Studies

Replication Management in Coda

Replication Management in Bayou

Amazon Dynamo

Concluding Remarks

Bibliographic Notes

Exercises

Self-Stabilizing Systems

Introduction

Theoretical Foundations

Stabilizing Mutual Exclusion

Mutual Exclusion on a Unidirectional Ring

Mutual Exclusion on a Bidirectional Array

Stabilizing Graph Coloring

Stabilizing Spanning Tree Protocol

Stabilizing Maximal Matching 377

Distributed Reset

Stabilizing Clock Phase Synchronization

Concluding Remarks

Bibliographic Notes

Exercises

Section V: Real-World Issues

Distributed Discrete-Event Simulation

Introduction

Event-Driven Simulation

Distributed Simulation

Challenges

Correctness Issues

Conservative Simulation

Optimistic Simulation and Time Warp

Global Virtual Time

Concluding Remarks

Bibliographic Notes

Exercises

Security in Distributed Systems

Introduction

Security Mechanisms

Common Security Attacks

Eavesdropping

Denial of Service

Data Tampering

Masquerading

Man in the Middle

Malicious Software

Encryption

Secret Key Cryptosystem

Confusion and Diffusion

DES

AES

One-Time Pad

Stream Ciphers

Steganography

Public Key Cryptosystems

Rivest–Shamir–Adleman Cryptosystem

ElGamal Cryptosystem

Digital Signatures

Signatures in Secret-Key Cryptosystems

Signatures in Public-Key Cryptosystems

Hashing Algorithms

Birthday Attack

Elliptic Curve Cryptography

Authentication Server

Authentication Service for Secret-Key Cryptosystems

Authentication Server for Public-Key Systems

Digital Certificates

Case Studies

Kerberos

Pretty Good Privacy

Secure Socket Layer

Virtual Private Networks and Firewalls

Virtual Private Network

Firewall

Sharing a Secret

Concluding Remarks

Bibliographic Notes

Exercises

Sensor Networks

Vision

Architecture of Sensor Nodes

MICA Mote

ZigBee-Enabled Sensor Nodes

TinyOS® Operating System

Challenges in Wireless Sensor Networks

Energy Conservation

Fault Tolerance

Routing

Time Synchronization

Location Management

Middleware Design

Security

Routing Algorithms

Directed Diffusion

Cluster-Based Routing

Metadata-Based Routing: SPIN

Time Synchronization Using Reference Broadcast

Reference Broadcast

Localization Algorithms

RSSI-Based Ranging

Ranging Using Time Difference of Arrival

Anchor-Based Ranging

Security in Sensor Networks

SPIN for Data Security

Attacks on Routing

Applications

Health-Care Applications

Environment Monitoring and Control

Citizen Sensing

Pursuer–Evader Game

Concluding Remarks

Bibliographic Notes

Exercises

Social and Peer-to-Peer Networks

Introduction to Social Networks

Milgram’s Experiment

Metrics of Social Networks

Clustering Coefficient

Diameter

Modeling Social Networks

Erdös–Rényi Model

Small-World Model

Power-Law Graphs

Centrality Measures in Social Networks

Degree Centrality

Closeness Centrality

Betweenness Centrality

Community Detection

Girvan–Newman Algorithm

Introduction to Peer-to-Peer Networks

First -Generation P2P Systems

Napster

Gnutella

Second-Generation P2P Systems

KaZaA

Chord

Content-Addressable Network

Pastry

Koorde and De Bruijn Graph

Skip Graph

Replication Management

BitTorrent and Free Riding

Censorship Resistance, Anonymity

Concluding Remarks

Bibliographic Notes

Exercises

References

Index

About the Author

Sukumar Ghosh has been a professor in the Department of Computer Science at the University of Iowa, Iowa City, USA since 1995. He earned his Ph.D in computer science and engineering from Calcutta University, India in 1971, and completed his postdoctoral research at the University of Dortmund, Germany as an Alexander von Humboldt Foundation fellow. His current research interests are in distributed systems, with a special emphasis on dynamic distributed systems; fault-tolerant, self-stabilizing, and autonomic distributed systems; and peer-to-peer networks. He has published over 100 research papers and 5 book chapters on these topics, and has supervised 16 Ph.D students.

About the Series

Chapman & Hall/CRC Computer and Information Science Series

Learn more…

Subject Categories

BISAC Subject Codes/Headings:
COM059000
COMPUTERS / Computer Engineering
MAT000000
MATHEMATICS / General
MAT004000
MATHEMATICS / Arithmetic