內容提要

《分散式算法》對分散式算法進行全面介紹,包括最為重要的算法和不可能性結果。絕大部分的解都給出了數學證明。這些算法都根據精確定義的複雜度衡量方法進行分析。《分散式算法》還講述了針對許多典型問題的算法、各類系統模型及其能力。章後提供大量習題並列出了詳細的參考文獻。《分散式算法》可作為高等院校計算機系統性研究生的教材,尤其是適合對計算機理論或體系結構感興趣的學生學習,還適合分散式設計人員,研究人員及其相關技術人員參考。
作者簡介:
NancyA.Lynch是麻省理工學院電子工程和計算機科學系的教授,領導麻省理工學院的分散式系統理論研究組。在分散式算法和不可能解以及分散式系統的形式化建模和證明方面,她編寫了大量的著作。
目錄
出版者的話
專家指導委員會
譯者序
前言
第1章引言
1.1相關主題
1.2我們的觀點
1.3本書內容綜述
1.4參考文獻注釋
1.5標記
第一部分同步網路算法
第2章建模1:同步網路模型
2.1同步網路系統
2.2故障
2.3輸入和輸出
2.4運行
2.5證明方法
2.6複雜度度量
2.7隨機化
2.8參考文獻注釋
第3章同步環中的領導者選擇
3.1問題
3.2相同進程的不可能性結果
3.3基本算法
3.4通信複雜度為的算法
3.5非基於比較的算法
3.6基於比較的算法的手段
3.7非基於比較的算法的的下界
3.8參考文獻注釋
3.9習題
第4章一般同步網路中的算法
4.1一般網路中的領導者的算法
4.2廣度優先搜尋
4.3最短路徑
4.4最站生成樹
4.5最大獨立集
4.6參考文獻注釋
4.7習題
第5章鏈路故障時的分散式一致性
5.1協同攻擊問題確定性版本
5.2協同攻擊問題隨機化版本
5.3參考文獻注釋
5.4習題
第6章進程故障下的分散式一致性
6.1問題
6.2針對停止故障的算法
6.3針對故障的算法
6.4減小通信開銷
6.5一致性問題中的個數
6.6一般圖中的一致性問題
6.7
盤點有關算法書籍
算法可以理解為有基本運算及規定的運算順序所構成的完整的解題步驟。或者看成按照要求設計好的有限的確切的計算序列,並且這樣的步驟和序列可以解決一類問題。 |