分散式演算法(典藏版)/電腦科學叢書

作者：(美)南希·A.林奇|責編:曲熠|譯者:舒繼武//李國東//余華山
出版社：機械工業
ISBN：9787111724247

出版日期：2023/05/01
裝幀：平裝
頁數：518

人民幣：RMB 119 元售價：元

內容大鋼

本書對分散式演算法進行全面介紹，包含同步模型、非同步模型和部分同步模型，針對這些模型討論互斥性、一致性和通信問題，為設計、實現和分析分散式演算法提供了藍圖，適合學生、程序員、系統分析人員和研究人員等不同類型的讀者閱讀。書中涉及該領域重要的演算法和不可能解，而且採用簡單的自動機理論進行論述，其中涉及的問題包括資源分配、通信、分散式處理器之間的一致性、數據一致性、死鎖檢測、領導者進程的選取、全局快照等。

作者介紹

(美)南希·A.林奇|責編:曲熠|譯者:舒繼武//李國東//余華山
南希·A.林奇（Nancy A.Lynch）　麻省理工學院電子工程和電腦科學系教授，領導麻省理工學院的分散式系統理論研究組，在分散式演算法和不可能解以及分散式系統的形式化建模和證明方面編寫了大量著作。

譯者序
前言
  第1章  引言
    1.1  相關主題
    1.2  我們的觀點
    1.3  本書內容綜述
    1.4  參考文獻註釋
    1.5  標記
第一部分  同步網路演算法
  第2章  建模I：同步網路模型
    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  通信複雜度為O (nlogn）的演算法
    3.5  非基於比較的演算法
      3.5.1  時間片演算法
      3.5.2  變速演算法
    3.6  基於比較的演算法的下界
    3.7  非基於比較的演算法的下界*
    3.8  參考文獻註釋
    3.9  習題
  第4章  一般同步網路中的演算法
    4.1  一般網路中的領導者選舉
      4.1.1  問題
      4.1.2  簡單的洪泛演算法
      4.1.3  降低通信複雜度
    4.2  廣度優先搜索
      4.2.1  問題
      4.2.2  基本的廣度優先搜索演算法
      4.2.3  應用
    4.3  最短路徑
    4.4  最小生成樹
      4.4.1  問題
      4.4.2  基本定理
      4.4.3  演算法
    4.5  獨立集
      4.5.1  問題
      4.5.2  隨機化演算法
      4.5.3  分析*
    4.6  參考文獻註釋
    4.7  習題

  第5章  鏈路故障時的分散式一致性
    5.1  協同攻擊問題—確定性版本
    5.2  協同攻擊問題—隨機化版本
      5.2.1  形式化模型
      5.2.2  演算法
      5.2.3  不一致的下限
    5.3  參考文獻註釋
    5.4  習題
  第6章  進程故障下的分散式一致性
    6.1  問題
    6.2  針對停止故障的演算法
      6.2.1  基本演算法
      6.2.2  減少通信
      6.2.3  指數信息收集演算法
      6.2.4  帶鑒別的Byzantine一致性
    6.3  針對Byzantine故障的演算法
      6.3.1  舉例
      6.3.2  Byzantine一致性問題的EIG演算法
      6.3.3  使用二元Byzantine一致性的一般Byzantine一致性問題
      6.3.4  減少通信開銷
    6.4  Byzantine一致性問題中進程的個數
    6.5  一般圖中的Byzantine一致性問題
    6.6  弱Byzantine一致性
    6.7  有停止故障時的輪數
    6.8  參考文獻註釋
    6.9  習題
  第7章  更多的一致性問題
    7.1  k一致性問題
      7.1.1  問題
      7.1.2  演算法
      7.1.3  下界*
    7.2  近似一致性
    7.3  提交問題
      7.3.1  問題
      7.3.2  兩階段提交
      7.3.3  三階段提交
      7.3.4  消息數的下界
    7.4  參考文獻註釋
    7.5  習題
第二部分  非同步演算法
  第8章  建模II：非同步系統模型
    8.1  輸入/輸出自動機
    8.2  自動機的操作
      8.2.1  合成
      8.2.2  隱藏
    8.3  公平性
    8.4  問題的輸入和輸出
    8.5  屬性與證明方法
      8.5.1  不變式斷言
      8.5.2  軌跡屬性

      8.5.3  安全與活性屬性
      8.5.4  合成推理
      8.5.5  層次化證明
    8.6  複雜度衡量
    8.7  不可區分的運行
    8.8  隨機化
    8.9  參考文獻註釋
    8.10  習題
第二部分A  非同步共享存儲器演算法
  第9章  建模III：非同步共享存儲器模型
    9.1  共享存儲器系統
    9.2  環境模型
    9.3  不可區分狀態
    9.4  共享變數類型
    9.5  複雜度衡量
    9.6  故障
    9.7  隨機化
    9.8  參考文獻註釋
    9.9  習題
  第10章  互斥
    10.1  非同步共享存儲器模型
    10.2  問題
    10.3  Dijkstra的互斥演算法
      10.3.1  演算法
      10.3.2  正確性證明
      10.3.3  互斥條件的一個斷言式證明
      10.3.4  運行時間
    10.4  互斥演算法的更強條件
    10.5  鎖定權互斥演算法
      10.5.1  雙進程演算法
      10.5.2  n進程演算法
      10.5.3  錦標賽演算法
    10.6  使用單寫者共享寄存器的演算法
    10.7  Bakery演算法
    10.8  寄存器數量的下界
      10.8.1  基本事實
      10.8.2  單寫者共享變數
      10.8.3  多寫者共享變數
    10.9  使用讀–改–寫共享變數的互斥
      10.9.1  基本問題
      10.9.2  有界繞過次數
      10.9.3  鎖定權
      10.9.4  模擬證明
    10.10  參考文獻註釋
    10.11  習題
  第11章  資源分配
    11.1  ?問題
      11.1.1  顯式資源規格說明和互斥規格說明
      11.1.2  資源分配問題
      11.1.3  哲學家用餐問題

      11.1.4  解法的受限形式
    11.2  對稱哲學家用餐演算法的不存在性
    11.3  右–左哲學家用餐演算法
      11.3.1  等待鏈
      11.3.2  基本演算法
      11.3.3  擴展
    11.4  隨機哲學家用餐演算法*
      11.4.1  演算法*
      11.4.2  正確性*
    11.5  參考文獻註釋
    11.6  習題
  第12章  一致性
    12.1  問題
    12.2  使用讀/寫共享存儲器的一致性問題
      12.2.1  限制
      12.2.2  術語
      12.2.3  雙價初始化
      12.2.4  無等待終止性的不可能性
      12.2.5  單故障終止性的不可能性結果
    12.3  讀/改/寫共享存儲器上的一致性問題
    12.4  其他共享存儲器類型
    12.5  非同步共享存儲器系統中的可計算性*
    12.6  參考文獻註釋
    12.7  習題
  第13章  原子對象
    13.1  定義和基本結論
      13.1.1  原子對象的定義
      13.1.2  規範無等待原子對象自動機
      13.1.3  原子對象的合成
      13.1.4  原子對象和共享變數
      13.1.5  顯示原子性的一個充分條件
    13.2  用讀/寫變數實現讀–改–寫原子對象
    13.3  共享存儲器的原子快照
      13.3.1  問題
      13.3.2  帶無界變數的一個演算法
      13.3.3  帶有界變數的一個演算法*
    13.4  讀/寫原子對象
      13.4.1  問題
      13.4.2  證明原子性的其他引理
      13.4.3  帶無界變數的一個演算法
      13.4.4  兩個寫者的有界演算法
      13.4.5  使用快照的演算法
    13.5  參考文獻註釋
    13.6  習題
第二部分B  非同步網路演算法
  第14章  建模IV：非同步網路模型
    14.1  發送/接收系統
      14.1.1  進程
      14.1.2  發送/接收通道
      14.1.3  非同步發送/接收系統

      14.1.4  使用可靠FIFO通道的發送接收系統的屬性
      14.1.5  複雜度度量
    14.2  廣播系統
      14.2.1  進程
      14.2.2  廣播通道
      14.2.3  非同步廣播系統
      14.2.4  採用可靠廣播通道的廣播系統的屬性
      14.2.5  複雜度度量
    14.3  多播系統
      14.3.1  進程
      14.3.2  多播通道
      14.3.3  非同步多播系統
    14.4  參考文獻註釋
    14.5  習題
  第15章  基本非同步網路演算法
    15.1  環中的領導者選舉
      15.1.1  LCR演算法
      15.1.2  HS演算法
      15.1.3  PetersonLeader演算法
      15.1.4  通信複雜度的下界
    15.2  任意網路中的領導者選舉
    15.3  生成樹的構造、廣播和斂播
    15.4  廣度優先搜索和最短路徑
    15.5  最小生成樹
      15.5.1  問題描述
      15.5.2  同步演算法：回顧
      15.5.3  GHS演算法：概要
      15.5.4  更詳細的演算法
      15.5.5  特殊消息
      15.5.6  複雜度分析
      15.5.7  GHS演算法的正確性證明
      15.5.8  簡單「同步」策略
      15.5.9  應用到領導者選舉演算法中
    15.6  參考文獻註釋
    15.7  習題
  第16章  同步器
    16.1  問題
    16.2  局部同步器
    16.3  安全同步器
      16.3.1  前端自動機
      16.3.2  通道自動機
      16.3.3  安全同步器的任務
      16.3.4  正確性
    16.4  安全同步器的實現
      16.4.1  同步器Alpha
      16.4.2  同步器Beta
      16.4.3  同步器Gamma
    16.5  應用
      16.5.1  領導者選舉
      16.5.2  廣度優先搜索

      16.5.3  最短路徑
      16.5.4  廣播與確認
      16.5.5  獨立集
    16.6  時間下界
    16.7  參考文獻註釋
    16.8  習題
  第17章  共享存儲器與網路
    17.1  從非同步共享存儲器模型到非同步網路模型的轉換
      17.1.1  問題
      17.1.2  無故障時的策略
      17.1.3  容忍進程故障的演算法
      17.1.4  對於n/2故障的不可能性結果
    17.2  從非同步網路模型到非同步共享存儲器模型的轉換
      17.2.1  發送/接收系統
      17.2.2  廣播系統
      17.2.3  非同步網路中一致性的不可能性
    17.3  參考文獻註釋
    17.4  習題
  第18章  邏輯時間
    18.1  非同步網路的邏輯時間
      18.1.1  發送/接收系統
      18.1.2  廣播系統
    18.2  使用邏輯時間的非同步演算法
      18.2.1  時鐘的走動
      18.2.2  延遲未來事件
    18.3  應用
      18.3.1  銀行系統
      18.3.2  全局快照
      18.3.3  模擬一台單狀態機
    18.4  從實際時間演算法到邏輯時間演算法的變換*
    18.5  參考文獻註釋
    18.6  習題
  第19章  一致全局快照和穩定屬性檢測
    19.1  發散演算法的終止檢測
      19.1.1  問題
      19.1.2  DijkstraScholten演算法
    19.2  一致全局快照
      19.2.1  問題
      19.2.2  ChandyLamport演算法
      19.2.3  應用
    19.3  參考文獻註釋
    19.4  習題
  第20章  網路資源分配
    20.1  互斥
      20.1.1  問題
      20.1.2  模擬共享存儲器
      20.1.3  循環令牌演算法
      20.1.4  基於邏輯時間的演算法
      20.1.5  LogicalTimeME演算法的改進
    20.2  通用資源分配

      20.2.1  問題
      20.2.2  著色演算法
      20.2.3  基於邏輯時間的演算法
      20.2.4  無環有向圖演算法
      20.2.5  哲學家飲水*
    20.3  參考文獻註釋
    20.4  習題
  第21章  帶進程故障的非同步網路計算
    21.1  網路模型
    21.2  有故障環境中一致性的不可能性
    21.3  隨機演算法
    21.4  故障檢測器
    21.5  k一致性
    21.6  近似一致性
    21.7  非同步網路的計算能力*
    21.8  參考文獻註釋
    21.9  習題
  第22章  數據鏈路協議
    22.1  問題闡述
    22.2  Stenning協議
    22.3  位變換協議
    22.4  可容忍消息重排序的有界tag協議
      22.4.1  關於可容忍消息重排序和重複的不可能性結論
      22.4.2  可容忍消息丟失和重排序的有界tag協議
      22.4.3  不存在可容忍消息丟失和重排序的高效協議
    22.5  可容忍進程崩潰
      22.5.1  簡單的不可能性結論
      22.5.2  更複雜的不可能性結論
      22.5.3  實用的協議
    22.6  參考文獻註釋
    22.7  習題
第三部分  部分同步演算法
  第23章  建模V：部分同步系統模型
    23.1  MMT定時自動機
      23.1.1  基本定義
      23.1.2  操作
    23.2  通用定時自動機
      23.2.1  基本定義
      23.2.2  將MMT自動機轉化為通用定時自動機
      23.2.3  動作
    23.3  屬性和證明方法
      23.3.1  不變式斷言
      23.3.2  定時軌跡屬性
      23.3.3  模擬關係
    23.4  構造共享存儲器和網路系統的模型
      23.4.1  共享存儲器系統
      23.4.2  網路
    23.5  參考文獻註釋
    23.6  習題
  第24章  部分同步的互斥性

    24.1  問題
    24.2  單寄存器演算法
    24.3  對定時故障的恢復性
    24.4  不可能性結果
      24.4.1  時間下界
      24.4.2  最終時間界限的不可能性結果*
    24.5  參考文獻註釋
    24.6  習題
  第25章  部分同步的一致性
    25.1  問題
    25.2  故障檢測器
    25.3  基本結論
      25.3.1  上界
      25.3.2  下界
    25.4  有效演算法
      25.4.1  演算法
      25.4.2  安全屬性
      25.4.3  活性和複雜度
    25.5  涉及時間不確定性的下界*
    25.6  其他結果*
      25.6.1  同步進程、非同步通道*
      25.6.2  非同步進程、同步通道*
      25.6.3  最終時間界限*
    25.7  小結
    25.8  參考文獻註釋
    25.9  習題
  參考文獻

同類熱銷排行榜

最近瀏覽的商品

分散式演算法(典藏版)/電腦科學叢書