Skip to content

Distributed Computing Fundamentals, Simulations, and Advanced Topics

Spend $50 to get a free DVD!

ISBN-10: 0471453242

ISBN-13: 9780471453246

Edition: 2nd 2004 (Revised)

Authors: Hagit Attiya, Jennifer Welch

List price: $162.00
Shipping box This item qualifies for FREE shipping.
Blue ribbon 30 day, 100% satisfaction guarantee!
what's this?
Rush Rewards U
Members Receive:
Carrot Coin icon
XP icon
You have reached 400 XP and carrot coins. That is the daily max!

Description:

This work presents a comprehensive introduction to the fundamental results in the mathematical foundations of distributed computing.
Customers also bought

Book details

List price: $162.00
Edition: 2nd
Copyright year: 2004
Publisher: John Wiley & Sons, Incorporated
Publication date: 3/25/2004
Binding: Hardcover
Pages: 432
Size: 6.50" wide x 9.75" long x 1.00" tall
Weight: 1.628
Language: English

Introduction
Distributed Systems
Theory of Distributed Computing
Overview
Relationship of Theory to Practice
Fundamentals
Basic Algorithms in Message-Passing Systems
Formal Models for Message Passing Systems
Systems
Complexity Measures
Pseudocode Conventions
Broadcast and Convergecast on a Spanning Tree
Flooding and Building a Spanning Tree
Constructing a Depth-First Search Spanning Tree for a Specified Root
Constructing a Depth-First Search Spanning Tree without a Specified Root
Leader Election in Rings
The Leader Election Problem
Anonymous Rings
Asynchronous Rings
An O(n[superscript 2]) Algorithm
An O(n log n) Algorithm
An [Omega](n log n) Lower Bound
Synchronous Rings
An O(n) Upper Bound
An [Omega](n log n) Lower Bound for Restricted Algorithms
Mutual Exclusion in Shared Memory
Formal Model for Shared Memory Systems
Systems
Complexity Measures
Pseudocode Conventions
The Mutual Exclusion Problem
Mutual Exclusion Using Powerful Primitives
Binary Test&Set Registers
Read-Modify-Write Registers
Lower Bound on the Number of Memory States
Mutual Exclusion Using Read/Write Registers
The Bakery Algorithm
A Bounded Mutual Exclusion Algorithm for Two Processors
A Bounded Mutual Exclusion Algorithm for n Processors
Lower Bound on the Number of Read/Write Registers
Fast Mutual Exclusion
Fault-Tolerant Consensus
Synchronous Systems with Crash Failures
Formal Model
The Consensus Problem
A Simple Algorithm
Lower Bound on the Number of Rounds
Synchronous Systems with Byzantine Failures
Formal Model
The Consensus Problem Revisited
Lower Bound on the Ratio of Faulty Processors
An Exponential Algorithm
A Polynomial Algorithm
Impossibility in Asynchronous Systems
Shared Memory--The Wait-Free Case
Shared Memory--The General Case
Message Passing
Causality and Time
Capturing Causality
The Happens-Before Relation
Logical Clocks
Vector Clocks
Shared Memory Systems
Examples of Using Causality
Consistent Cuts
A Limitation of the Happens-Before Relation: The Session Problem
Clock Synchronization
Modeling Physical Clocks
The Clock Synchronization Problem
The Two Processors Case
An Upper Bound
A Lower Bound
Practical Clock Synchronization: Estimating Clock Differences
Simulations
A Formal Model for Simulations
Problem Specifications
Communication Systems
Asynchronous Point-to-Point Message Passing
Asynchronous Broadcast
Processes
Admissibility
Simulations
Pseudocode Conventions
Broadcast and Multicast
Specification of Broadcast Services
The Basic Service Specification
Broadcast Service Qualities
Implementing a Broadcast Service
Basic Broadcast Service
Single-Source FIFO Ordering
Totally Ordered Broadcast
Causality
Reliability
Multicast in Groups
Specification
Implementation
An Application: Replication
Replicated Database
The State Machine Approach
Distributed Shared Memory
Linearizable Shared Memory
Sequentially Consistent Shared Memory
Algorithms
Linearizability
Sequential Consistency
Lower Bounds
Adding Time and Clocks to the Layered Model
Sequential Consistency
Linearizability
Fault-Tolerant Simulations of Read/Write Objects
Fault-Tolerant Shared Memory Simulations
Simple Read/Write Register Simulations
Multi-Valued from Binary
Multi-Reader from Single-Reader
Multi-Writer from Single-Writer
Atomic Snapshot Objects
Handshaking Procedures
A Bounded Memory Simulation
Simulating Shared Registers in Message-Passing Systems
Simulating Synchrony
Synchronous Message-Passing Specification
Simulating Synchronous Processors
Simulating Synchronous Processors and Synchronous Communication
A Simple Synchronizer
Application: Constructing a Breadth-First Search Tree
Local vs. Global Simulations
Improving the Fault Tolerance of Algorithms
Overview
Modeling Synchronous Processors and Byzantine Failures
Simulating Identical Byzantine Failures on Top of Byzantine Failures
Definition of Identical Byzantine
Simulating Identical Byzantine
Simulating Omission Failures on Top of Identical Byzantine Failures
Definition of Omission
Simulating Omission
Simulating Crash Failures on Top of Omission Failures
Definition of Crash
Simulating Crash
Application: Consensus in the Presence of Byzantine Failures
Asynchronous Identical Byzantine on Top of Byzantine Failures
Definition of Asynchronous Identical Byzantine
Definition of Asynchronous Byzantine
Simulating Asynchronous Identical Byzantine
Fault-Tolerant Clock Synchronization
Problem Definition
The Ratio of Faulty Processors
A Clock Synchronization Algorithm
Timing Failures
Byzantine Failures
Practical Clock Synchronization: Identifying Faulty Clocks
Advanced Topics
Randomization
Leader Election: A Case Study
Weakening the Problem Definition
Synchronous One-Shot Algorithm
Synchronous Iterated Algorithm and Expectation
Asynchronous Systems and Adversaries
Impossibility of Uniform Algorithms
Summary of Probabilistic Definitions
Mutual Exclusion with Small Shared Variables
Consensus
The General Algorithm Scheme
A Common Coin with Constant Bias
Tolerating Byzantine Failures
Shared Memory Systems
Wait-Free Simulations of Arbitrary Objects
Example: A FIFO Queue
The Wait-Free Hierarchy
Universality
A Nonblocking Simulation Using Compare&Swap
A Nonblocking Algorithm Using Consensus Objects
A Wait-Free Algorithm Using Consensus Objects
Bounding the Memory Requirements
Handling Nondeterminism
Employing Randomized Consensus
Problems Solvable in Asynchronous Systems
k-Set Consensus
Approximate Agreement
Known Input Range
Unknown Input Range
Renaming
The Wait-Free Case
The General Case
Long-Lived Renaming
k-Exclusion and k-Assignment
An Algorithm for k-Exclusion
An Algorithm for k-Assignment
Solving Consensus in Eventually Stable Systems
Preserving Safety in Shared Memory Systems
Failure Detectors
Solving Consensus using Failure Detectors
Solving Consensus with [diamond]S
Solving Consensus with S
Solving Consensus with [Omega]
Implementing Failure Detectors
State Machine Replication with Failure Detectors
References
Index