Design and Analysis of Distributed Algorithms
暫譯: 分散式演算法的設計與分析

Nicola Santoro

Design and Analysis of Distributed Algorithms
  • 出版商: Wiley
  • 出版日期: 2006-10-27
  • 售價: $1,362
  • 語言: 英文
  • 頁數: 608
  • 裝訂: Hardcover
  • ISBN: 0471719978
  • ISBN-13: 9780471719977
  • 相關分類: Algorithms-data-structures

    • 下單後立即進貨 (約5~7天)

買這商品的人也買了...

相關主題

商品描述

Description

This text is based on a simple and fully reactive computational model that allows for intuitive comprehension and logical designs. The principles and techniques presented can be applied to any distributed computing environment (e.g., distributed systems, communication networks, data networks, grid networks, internet, etc.). The text provides a wealth of unique material for learning how to design algorithms and protocols perform tasks efficiently in a distributed computing environment.
 

Table of Contents

Preface.

1. Distributed Computing Environments.

1.1 Entities.

1.2 Communication.

1.3 Axioms and Restrictions.

1.3.1 Axioms.

1.3.2 Restrictions.

1.4 Cost and Complexity.

1.4.1 Amount of Communication Activities.

1.4.2 Time.

1.5 An Example: Broadcasting.

1.6 States and Events.

1.6.1 Time and Events.

1.6.2 States and Configurations.

1.7 Problems and Solutions (*).

1.8 Knowledge.

1.8.1 Levels of Knowledge.

1.8.2 Types of Knowledge.

1.9 Technical Considerations.

1.9.1 Messages.

1.9.2 Protocol.

1.9.3 Communication Mechanism.

1.10 Summary of Definitions.

1.11 Bibliographical Notes.

1.12 Exercises, Problems, and Answers.

1.12.1 Exercises and Problems.

1.12.2 Answers to Exercises.

2. Basic Problems And Protocols.

2.1 Broadcast.

2.1.1 The Problem.

2.1.2 Cost of Broadcasting.

2.1.3 Broadcasting in Special Networks.

2.2 Wake-Up.

2.2.1 Generic Wake-Up.

2.2.2 Wake-Up in Special Networks.

2.3 Traversal.

2.3.1 Depth-First Traversal.

2.3.2 Hacking (*).

2.3.3 Traversal in Special Networks.

2.3.4 Considerations on Traversal.

2.4 Practical Implications: Use a Subnet.

2.5 Constructing a Spanning Tree.

2.5.1 SPT Construction with a Single Initiator: Shout.

2.5.2 Other SPT Constructions with Single Initiator.

2.5.3 Considerations on the Constructed Tree.

2.5.4 Application: Better Traversal.

2.5.5 Spanning-Tree Construction with Multiple Initiators.

2.5.6 Impossibility Result.

2.5.7 SPT with Initial Distinct Values.

2.6 Computations in Trees.

2.6.1 Saturation: A Basic Technique.

2.6.2 Minimum Finding.

2.6.3 Distributed Function Evaluation.

2.6.4 Finding Eccentricities.

2.6.5 Center Finding.

2.6.6 Other Computations.

2.6.7 Computing in Rooted Trees.

2.7 Summary.

2.7.1 Summary of Problems.

2.7.2 Summary of Techniques.

2.8 Bibliographical Notes.

2.9 Exercises, Problems, and Answers.

2.9.1 Exercises.

2.9.2 Problems.

2.9.3 Answers to Exercises.

3. Election.

3.1 Introduction.

3.1.1 Impossibility Result.

3.1.2 Additional Restrictions.

3.1.3 Solution Strategies.

3.2 Election in Trees.

3.3 Election in Rings.

3.3.1 All the Way.

3.3.2 As Far As It Can.

3.3.3 Controlled Distance.

3.3.4 Electoral Stages.

3.3.5 Stages with Feedback.

3.3.6 Alternating Steps.

3.3.7 Unidirectional Protocols.

3.3.8 Limits to Improvements (*).

3.3.9 Summary and Lessons.

3.4 Election in Mesh Networks.

3.4.1 Meshes.

3.4.2 Tori.

3.5 Election in Cube Networks.

3.5.1 Oriented Hypercubes.

3.5.2 Unoriented Hypercubes.

3.6 Election in Complete Networks.

3.6.1 Stages and Territory.

3.6.2 Surprising Limitation.

3.6.3 Harvesting the Communication Power.

3.7 Election in Chordal Rings (*).

3.7.1 Chordal Rings.

3.7.2 Lower Bounds.

3.8 Universal Election Protocols.

3.8.1 Mega-Merger.

3.8.2 Analysis of Mega-Merger.

3.8.3 YO-YO.

3.8.4 Lower Bounds and Equivalences.

3.9 Bibliographical Notes.

3.10 Exercises, Problems, and Answers.

3.10.1 Exercises.

3.10.2 Problems.

3.10.3 Answers to Exercises.

4. Message Routing and Shortest Paths.

4.1 Introduction.

4.2 Shortest Path Routing.

4.2.1 Gossiping the Network Maps.

4.2.2 Iterative Construction of Routing Tables.

4.2.3 Constructing Shortest-Path Spanning Tree.

4.2.4 Constructing All-Pairs Shortest Paths.

4.2.5 Min-Hop Routing.

4.2.6 Suboptimal Solutions: Routing Trees.

4.3 Coping with Changes.

4.3.1 Adaptive Routing.

4.3.2 Fault-Tolerant Tables.

4.3.3 On Correctness and Guarantees.

4.4 Routing in Static Systems: Compact Tables.

4.4.1 The Size of Routing Tables.

4.4.2 Interval Routing.

4.5 Bibliographical Notes.

4.6 Exercises, Problems, and Answers.

4.6.1 Exercises.

4.6.2 Problems.

4.6.3 Answers to Exercises.

5. Distributed Set Operations.

5.1 Introduction.

5.2 Distributed Selection.

5.2.1 Order Statistics.

5.2.2 Selection in a Small Data Set.

5.2.3 Simple Case: Selection Among Two Sites.

5.2.4 General Selection Strategy: RankSelect.

5.2.5 Reducing the Worst Case: ReduceSelect.

5.3 Sorting a Distributed Set.

5.3.1 Distributed Sorting.

5.3.2 Special Case: Sorting on a Ordered Line.

5.3.3 Removing the Topological Constraints: Complete Graph.

5.3.4 Basic Limitations.

5.3.5 Efficient Sorting: SelectSort.

5.3.6 Unrestricted Sorting.

5.4 Distributed Sets Operations.

5.4.1 Operations on Distributed Sets.

5.4.2 Local Structure.

5.4.3 Local Evaluation (*).

5.4.4 Global Evaluation.

5.4.5 Operational Costs.

5.5 Bibliographical Notes.

5.6 Exercises, Problems, and Answers.

5.6.1 Exercises.

5.6.2 Problems.

5.6.3 Answers to Exercises.

6. Synchronous Computations.

6.1 Synchronous Distributed Computing.

6.1.1 Fully Synchronous Systems.

6.1.2 Clocks and Unit of Time.

6.1.3 Communication Delays and Size of Messages.

6.1.4 On the Unique Nature of Synchronous Computations.

6.1.5 The Cost of Synchronous Protocols.

6.2 Communicators, Pipeline, and Transformers.

6.2.1 Two-Party Communication.

6.2.2 Pipeline.

6.2.3 Transformers.

6.3 Min-Finding and Election: Waiting and Guessing.

6.3.1 Waiting.

6.3.2 Guessing.

6.3.3 Double Wait: Integrating Waiting and Guessing.

6.4 Synchronization Problems: Reset, Unison, and Firing Squad.

6.4.1 Reset /Wake-up.

6.4.2 Unison.

6.4.3 Firing Squad.

6.5 Bibliographical Notes.

6.6 Exercises, Problems, and Answers.

6.6.1 Exercises.

6.6.2 Problems.

6.6.3 Answers to Exercises.

7. Computing in Presence of Faults.

7.1 Introduction.

7.1.1 Faults and Failures.

7.1.2 Modelling Faults.

7.1.3 Topological Factors.

7.1.4 Fault Tolerance, Agreement, and Common Knowledge.

7.2 The Crushing Impact of Failures.

7.2.1 Node Failures: Single-Fault Disaster.

7.2.2 Consequences of the Single Fault Disaster.

7.3 Localized Entity Failures: Using Synchrony.

7.3.1 Synchronous Consensus with Crash Failures.

7.3.2 Synchronous Consensus with Byzantine Failures.

7.3.3 Limit to Number of Byzantine Entities for Agreement.

7.3.4 From Boolean to General Byzantine Agreement.

7.3.5 Byzantine Agreement in Arbitrary Graphs.

7.4 Localized Entity Failures: Using Randomization.

7.4.1 Random Actions and Coin Flips.

7.4.2 Randomized Asynchronous Consensus: Crash Failures.

7.4.3 Concluding Remarks.

7.5 Localized Entity Failures: Using Fault Detection.

7.5.1 Failure Detectors and Their Properties.

7.5.2 The Weakest Failure Detector.

7.6 Localized Entity Failures: Pre-Execution Failures.

7.6.1 Partial Reliability.

7.6.2 Example: Election in Complete Network.

7.7 Localized Link Failures.

7.7.1 A Tale of Two Synchronous Generals.

7.7.2 Computing With Faulty Links.

7.7.3 Concluding Remarks.

7.7.4 Considerations on Localized Entity Failures.

7.8 Ubiquitous Faults.

7.8.1 Communication Faults and Agreement.

7.8.2 Limits to Number of Ubiquitous Faults for Majority.

7.8.3 Unanimity in Spite of Ubiquitous Faults.

7.8.4 Tightness.

7.9 Bibliographical Notes.

7.10 Exercises, Problems, and Answers.

7.10.1 Exercises.

7.10.2 Problems.

7.10.3 Answers to Exercises.

8. Detecting Stable Properties.

8.1 Introduction.

8.2 Deadlock Detection.

8.2.1 Deadlock.

8.2.2 Detecting Deadlock: Wait-for Graph.

8.2.3 Single-Request Systems.

8.2.4 Multiple-Requests Systems.

8.2.5 Dynamic Wait-for Graphs.

8.2.6 Other Requests Systems.

8.3 Global Termination Detection.

8.3.1 A Simple Solution: Repeated Termination Queries.

8.3.2 Improved Protocols: Shrink.

8.3.3 Concluding Remarks.

8.4 Global Stable Property Detection.

8.4.1 General Strategy.

8.4.2 Time Cuts and Consistent Snapshots.

8.4.3 Computing A Consistent Snapshot.

8.4.4 Summary: Putting All Together.

8.5 Bibliographical Notes.

8.6 Exercises, Problems, and Answers.

8.6.1 Exercises.

8.6.2 Problems.

8.6.3 Answers to Exercises.

9. Continuous Computations.

9.1 Introduction.

9.2 Keeping Virtual Time.

9.2.1 Virtual Time and Causal Order.

9.2.2 Causal Order: Counter Clocks.

9.2.3 Complete Causal Order: Vector Clocks.

9.2.4 Concluding Remarks.

9.3 Distributed Mutual Exclusion.

9.3.1 The Problem.

9.3.2 A Simple And Efficient Solution.

9.3.3 Traversing the Network.

9.3.4 Managing a Distributed Queue.

9.3.5 Decentralized Permissions.

9.3.6 Mutual Exclusion in Complete Graphs: Quorum.

9.3.7 Concluding Remarks.

9.4 Deadlock: System Detection and Resolution.

9.4.1 System Detection and Resolution.

9.4.2 Detection and Resolution in Single-Request Systems.

9.4.3 Detection and Resolution in Multiple-Requests Systems.

9.5 Bibliographical Notes.

9.6 Exercises, Problems, and Answers.

9.6.1 Exercises.

9.6.2 Problems.

9.6.3 Answers to Exercises.

Index.

商品描述(中文翻譯)

# 描述
這段文字基於一個簡單且完全反應式的計算模型，允許直觀理解和邏輯設計。所提出的原則和技術可以應用於任何分散式計算環境（例如，分散式系統、通信網絡、數據網絡、網格網絡、互聯網等）。該文本提供了豐富的獨特材料，幫助學習如何在分散式計算環境中設計算法和協議，以高效執行任務。

# 目錄
**前言。**

**1. 分散式計算環境。**
1.1 實體。
1.2 通信。
1.3 公理與限制。
1.3.1 公理。
1.3.2 限制。
1.4 成本與複雜性。
1.4.1 通信活動的數量。
1.4.2 時間。
1.5 一個例子：廣播。
1.6 狀態與事件。
1.6.1 時間與事件。
1.6.2 狀態與配置。
1.7 問題與解決方案（*）。
1.8 知識。
1.8.1 知識的層次。
1.8.2 知識的類型。
1.9 技術考量。
1.9.1 消息。
1.9.2 協議。
1.9.3 通信機制。
1.10 定義摘要。
1.11 參考文獻說明。
1.12 練習、問題與答案。
1.12.1 練習與問題。
1.12.2 練習答案。

**2. 基本問題與協議。**
2.1 廣播。
2.1.1 問題。
2.1.2 廣播的成本。
2.1.3 特殊網絡中的廣播。
2.2 喚醒。
2.2.1 通用喚醒。
2.2.2 特殊網絡中的喚醒。
2.3 遍歷。
2.3.1 深度優先遍歷。
2.3.2 破解（*）。
2.3.3 特殊網絡中的遍歷。
2.3.4 遍歷考量。
2.4 實際應用：使用子網。
2.5 構建生成樹。
2.5.1 單一發起者的最短路徑樹構建：大喊。
2.5.2 其他單一發起者的最短路徑樹構建。
2.5.3 構建樹的考量。
2.5.4 應用：更好的遍歷。
2.5.5 多個發起者的生成樹構建。
2.5.6 不可能性結果。
2.5.7 具有初始不同值的最短路徑樹。
2.6 樹中的計算。
2.6.1 飽和：基本技術。
2.6.2 最小值查找。
2.6.3 分散式函數評估。
2.6.4 查找偏心性。
2.6.5 查找中心。
2.6.6 其他計算。
2.6.7 在根樹中的計算。
2.7 摘要。
2.7.1 問題摘要。
2.7.2 技術摘要。
2.8 參考文獻說明。
2.9 練習、問題與答案。
2.9.1 練習。
2.9.2 問題。
2.9.3 練習答案。

**3. 選舉。**
3.1 介紹。
3.1.1 不可能性結果。
3.1.2 附加限制。
3.1.3 解決策略。
3.2 樹中的選舉。
3.3 環中的選舉。
3.3.1 一路到底。
3.3.2 盡可能遠。
3.3.3 控制距離。
3.3.4 選舉階段。
3.3.5 具有反饋的階段。
3.3.6 交替步驟。
3.3.7 單向協議。
3.3.8 改進的限制（*）。
3.3.9 摘要與教訓。
3.4 網格網絡中的選舉。
3.4.1 網格。
3.4.2 圈。
3.5 立方體網絡中的選舉。
3.5.1 定向超立方體。
3.5.2 非定向超立方體。
3.6 完全網絡中的選舉。
3.6.1 階段與領域。
3.6.2 驚人的限制。
3.6.3 收穫通信能力。
3.7 和弦環中的選舉（*）。
3.7.1 和弦環。
3.7.2 下界。
3.8 通用選舉協議。
3.8.1 巨型合併。
3.8.2 巨型合併的分析。
3.8.3 YO-YO。
3.8.4 下界與等價性。
3.9 參考文獻說明。
3.10 練習、問題與答案。
3.10.1 練習。
3.10.2 問題。
3.10.3 練習答案。

**4. 消息路由與最短路徑。**
4.1 介紹。
4.2 最短路徑路由。
4.2.1 傳播網絡地圖。
4.2.2 路由表的迭代構建。
4.2.3 構建最短路徑生成樹。
4.2.4 構建所有對最短路徑。
4.2.5 最小跳數路由。
4.2.6 次優解：路由樹。
4.3 應對變化。
4.3.1 自適應路由。
4.3.2 容錯表。
4.3.3 關於正確性與保證。
4.4 靜態系統中的路由：緊湊表。
4.4.1 路由表的大小。
4.4.2 區間路由。
4.5 參考文獻說明。
4.6 練習、問題與答案。
4.6.1 練習。
4.6.2 問題。
4.6.3 練習答案。

**5. 分散式集合操作。**
5.1 介紹。
5.2 分散式選擇。
5.2.1 順序統計。
5.2.2 小數據集中的選擇。
5.2.3 簡單情況：在兩個站點之間的選擇。
5.2.4 一般選擇策略：RankSelect。
5.2.5 減少最壞情況：ReduceSelect。
5.3 排序分散式集合。
5.3.1 分散式排序。
5.3.2 特殊情況：在有序線上的排序。
5.3.3 移除拓撲約束：完全圖。
5.3.4 基本限制。
5.3.5 高效排序：SelectSort。
5.3.6 無限制排序。
5.4 分散式集合操作。
5.4.1 在分散式集合上的操作。
5.4.2 本地結構。
5.4.3 本地評估（*）。
5.4.4 全局評估。
5.4.5 操作成本。
5.5 參考文獻說明。
5.6 練習、問題與答案。
5.6.1 練習。
5.6.2 問題。
5.6.3 練習答案。

**6. 同步計算。**
6.1 同步分散式計算。
6.1.1 完全同步系統。
6.1.2 時鐘。

類似商品