關(guān)于我們
書單推薦
新書推薦
|
分布式算法(典藏版)
本書對分布式算法進(jìn)行了全面介紹,包括同步模型、異步模型和部分同步模型,針對這些模型討論互斥性、一致性和通信問題,為設(shè)計、實現(xiàn)和分析分布式算法提供了藍(lán)圖。本書對分布式算法領(lǐng)域的許多經(jīng)典問題給出了多種解決算法或者不可能性結(jié)果,絕大部分的算法附有詳細(xì)的證明過程,并且有jing確的復(fù)雜度衡量。本書還配有大量習(xí)題,并在每章后列出了詳細(xì)的參考文獻(xiàn)。本書可作為高等院校計算機(jī)專業(yè)的研究生教材,尤其適合對計算機(jī)理論或體系結(jié)構(gòu)感興趣的學(xué)生學(xué)習(xí),還適合分布式領(lǐng)域的設(shè)計人員和研究人員參考。
前 言
Distributed Algorithms 分布式算法是用于解決多個互連處理器運行問題的算法。分布式算法的各部分并發(fā)和獨立地運行,每一部分只承載有限的信息。即使處理器和通信信道以不同的速度運作,或即使某些構(gòu)件出了故障,這些算法仍然應(yīng)該正常運行。 分布式算法有廣泛的應(yīng)用:電信、分布式信息處理、科學(xué)計算以及實時進(jìn)程控制。例如,電話系統(tǒng)、航班訂票系統(tǒng)、銀行系統(tǒng)、全球信息系統(tǒng)、天氣預(yù)報系統(tǒng)以及飛機(jī)和核電站控制系統(tǒng)都嚴(yán)重依賴于分布式算法。很明顯,確保分布式算法準(zhǔn)確、高效地運行是非常重要的。然而,由于這種算法的執(zhí)行環(huán)境很復(fù)雜,所以設(shè)計分布式算法就成了一項困難的 任務(wù)。 本書對分布式算法這個領(lǐng)域做了全面的介紹,包括為重要的算法和不可能性結(jié)果,且都在一種簡單的自動機(jī)理論環(huán)境中呈現(xiàn)。幾乎所有的解都附有數(shù)學(xué)證明(至少是粗略的)。每個算法都根據(jù)精確定義的復(fù)雜度衡量方法進(jìn)行了分析?傊,這些內(nèi)容為更深入地理解分布式算法打下了牢固的基礎(chǔ)。 本書面向不同層次的讀者。首先,本書可以作為計算機(jī)系一年級研究生的教材,尤其適合于對計算機(jī)系統(tǒng)、理論或兩者懷有濃厚興趣的學(xué)生學(xué)習(xí)。其次,本書可作為分布式系統(tǒng)設(shè)計人員的短期培訓(xùn)教材。后,它也可作為參考手冊,供設(shè)計人員、學(xué)生、研究人員以及任何對該領(lǐng)域感興趣的人使用。 本書包含了針對很多典型問題的算法,如在幾種不同系統(tǒng)環(huán)境下的一致性(consensus)、通信、資源分配和同步問題。這些算法和相應(yīng)結(jié)果基于分布式環(huán)境的基本假設(shè)來組織。組織的層基于時序模型(timing model)—同步、異步或部分同步;第二層基于進(jìn)程間的通信機(jī)制—共享存儲器或消息傳遞。每種系統(tǒng)模型都用數(shù)章來闡述:每一部分的頭一章提出所述系統(tǒng)類型的形式化模型,余下各章介紹算法和不可能性結(jié)果。從頭至尾,本書進(jìn)行了嚴(yán)密的論述,然而非常簡明易懂。 由于該領(lǐng)域很廣闊,變化也很快,因此本書并不包羅萬象,只包括根本的結(jié)果。若以復(fù)雜度來衡量,這些結(jié)果并不總是的,但它們比較簡單且能夠闡明重要的通用設(shè)計和推理方法。 本書將會介紹分布式計算領(lǐng)域中許多重要的問題、算法和不可能性結(jié)果。當(dāng)實際系統(tǒng)中出現(xiàn)這些問題的時候,你就能將它們識別出來,并進(jìn)而利用本書介紹的算法來解決它們,或者應(yīng)用不可能性結(jié)果來證明它們是不可解的。本書還介紹各類系統(tǒng)模型及其能力。這樣一來,你自己就可以設(shè)計出新算法(甚至還可以證明出新的不可能性結(jié)果)。后,本書還會讓你相信,嚴(yán)格推導(dǎo)分布式算法和系統(tǒng)是可行的:形式化建模,給出其所需行為的精確規(guī)格說明,嚴(yán)格證明它們符合規(guī)格說明,確定合適的復(fù)雜度衡量標(biāo)準(zhǔn)以及按照這些標(biāo)準(zhǔn)進(jìn)行分析。 使用本書 預(yù)備知識 閱讀本書需要對基本的本科離散數(shù)學(xué)(包括數(shù)學(xué)歸納和漸近分析)、一些編程技能以及計算機(jī)系統(tǒng)相當(dāng)熟悉。有關(guān)隨機(jī)算法的部分還需要基本的概率知識。有關(guān)串行算法及其分析的本科課程對閱讀本書有幫助,但并不是必要的。 章節(jié)關(guān)系 本書的編排原則是使讀者能比較獨立地閱讀不同模型的各章內(nèi)容。各章之間的依賴關(guān)系如圖A所示。例如,如果想盡快了解異步網(wǎng)絡(luò),就可以跳過第5~7章。還可以只讀算法部分,而不必先閱讀算法所依賴的建模部分。 圖A 各章之間的依賴關(guān)系 帶星號的小節(jié) 在本書中,有幾個小節(jié)的標(biāo)題打了星號。它們的內(nèi)容不太基本或者說比其他部分更深。次閱讀的時候可以忽略這些內(nèi)容而不會有什么影響。 課程 本書的第1版已經(jīng)在MIT(麻省理工學(xué)院)的研究生導(dǎo)論課中用了很多年,并且在一些計算機(jī)軟件和應(yīng)用公司的系統(tǒng)設(shè)計師夏季課程中用了三年。本書包括足夠一年課程的內(nèi)容,所以對一些短期課程來說必須有所取舍(注意看章節(jié)之間的關(guān)系)。 例如,在學(xué)習(xí)異步網(wǎng)絡(luò)計算的一個學(xué)期的課程中,可以選擇第3、4、6章,7.2節(jié),第12章和第14~21章,參考一些有關(guān)建模的章節(jié)(第2、8和9章),并根據(jù)需要加入第10、11和13章中的一些定義。在學(xué)習(xí)分布一致性的一個學(xué)期的課程中,可以選擇第2~9章、第12章、13.1節(jié),以及第15、17、21、23和25章。還有其他多種可能組合。如果你是這個領(lǐng)域的研究者,你可以用所在領(lǐng)域的更新或者更特別的研究結(jié)果來補(bǔ)充本書。 在為系統(tǒng)設(shè)計師提供的一兩周的短期課程中,可以突出所有章節(jié)的重點,在較高的層次上討論關(guān)鍵結(jié)果和關(guān)鍵證明思想,而無須講解太多細(xì)節(jié)。 錯誤 如果在本書中發(fā)現(xiàn)了錯誤,或者對本書有什么建設(shè)性建議,請告訴我。特別歡迎對額外問題的建議。請發(fā)送email到distalgs@theory.lcs.mit.edu。 致謝 我很難一一列舉出所有對本書的出版做出貢獻(xiàn)的人們,因為本書是多年教學(xué)和研究的成果,得到了許多學(xué)生和研究人員的幫助。即使這樣,我還是想盡力而為。 本書是MIT的研究生課程6.852(分布式算法)講稿的終版本。在我早期組織素材的過程中,學(xué)生們學(xué)過這門課。這些學(xué)生在1990年和1992年幫助我完成了講稿的在線版本。有幾位課程助教對我整理筆記給予了極大的幫助,他們是Ken Goldman、Isaac Saias和Boaz Patt-Shamir。助教Jennifer Welch 和Rainer Gawlick也幫了我很大的忙。 許多同事和學(xué)生與我一起研究過本書中的一些結(jié)果,與我一起討論了其他人的工作,這對我充分理解素材幫助很大。其中包括Yehuda Afek、Eshrat Arjomandi、Hagit Attiya、Baruch Awerbuch、Bard Bloom、Alan Borodin、James Burns、Soma Chaudhuri、Brian Coan、Harish Devarajan、Danny Dolev、Cynthia Dwork、Alan Fekete、Michael Fischer、Greg Frederickson、Eli Gafni、Rainer Gawlick、Ken Goldman、Art Harvey、Maurice Herlihy、Paul Jackson、Jon Kleinberg、Leslie Lamport、Butler Lampson、Victor Luchangco、Yishay Mansour、Michael Merritt、Michael Paterson、Boaz Patt-Shamir、Gary Peterson、Shlomit Pinter、Stephen Ponzio、Isaac Saias、Russel Schaffer、Roberto Segala、Nir Shavit、Liuba Shrira、J?rgen S?gaard-Andersen、Eugene Stark、Larry Stockmeyer、Mark Tuttle、Frits Vaandrager、George Varghese、Bill Weihl、Jennifer Welch和Lenore Zuck。尤其感謝其中的兩位:我的導(dǎo)師Michael Fischer和我的學(xué)生Mark Tuttle。從1978年開始,Michael就與我一起致力于研究這個當(dāng)時還很小但看起來很有前途的領(lǐng)域,而Mark Tuttle的碩士論文定義并發(fā)展了I/O自動機(jī)模型。 我還要感謝Ajoy Datta、Roberto De Prisco、Alan Fekete、Faith Fich、Rainer Gawlick、Shai Halevi、Jon Kleinberg、Richard Ladner、John Leo、Victor Luchangco、Michael Melliar-Smith、Michael Merritt、Daniele Micciancio、Boaz Patt-Shamir、Anya Pogosyants、Stephen Ponzio、Sergio Rajsbaum、Roberto Segala、Nir Shavit、Mark Smith、Larry Stockmeyer、Mark Tuttle、George Varghese、Jennifer Welch和Lenore Zuck,他們審閱了全書的各部分草稿并提出了很多有用的建議。特別是Ajoy、Faith和George,他們使用本書的早期版本作為教材來教學(xué),給出了很多寶貴的意見。此外,我要感謝 Joanne Talbot 不厭其煩地排版、畫圖、搜集參考文獻(xiàn),以及不停地打印文稿等。David Jones也參與了排版工作。在此, 我還要感謝 John Guttag、Paul Penfield 和其他MIT EECS的成員,他們?yōu)槲野才帕藢憰臅r間。Morgan Kaufmann的Bruce Spatz又一次鼓勵并幫助我做這個艱巨的工作,他總能給我正確的建議。在本書后付梓階段,Morgan Kaufmann的Julie Pabst和Diane Cerra給了我很大幫助。同時,也感謝Babel出版社的Ed Sznyter的LATEX技術(shù)。 后也是重要的,我要感謝體貼我的家人Dennis、Patrick和Mary Lynch,他們體諒我為本書所做的一切工作,同時幫我處理了其他的事情。特別感謝Dennis,當(dāng)我把大部分時間花在計算機(jī)前時,Dennis在為我準(zhǔn)備美味的海鮮晚餐,甚至把我的浴室和洗衣房翻修 一新! Nancy A. Lynch Cambridge, Massachusetts
南!. 林奇(Nancy A. Lynch) 麻省理工學(xué)院電子工程和計算機(jī)科學(xué)系教授,領(lǐng)導(dǎo)麻省理工學(xué)院的分布式系統(tǒng)理論研究組,在分布式算法和不可能解以及分布式系統(tǒng)的形式化建模和證明方面編寫了大量著作。
目 錄
Distributed Algorithms 譯者序 前言 第1章 引言 1 1.1 相關(guān)主題 1 1.2 我們的觀點 2 1.3 本書內(nèi)容綜述 4 1.4 參考文獻(xiàn)注釋 7 1.5 標(biāo)記 8 部分 同步網(wǎng)絡(luò)算法 第2章 建模I:同步網(wǎng)絡(luò)模型 10 2.1 同步網(wǎng)絡(luò)系統(tǒng) 10 2.2 故障 11 2.3 輸入和輸出 11 2.4 運行 12 2.5 證明方法 12 2.6 復(fù)雜度度量 12 2.7 隨機(jī)化 13 2.8 參考文獻(xiàn)注釋 13 第3章 同步環(huán)中的領(lǐng)導(dǎo)者選擇 14 3.1 問題 14 3.2 相同進(jìn)程的不可能性結(jié)果 15 3.3 基本算法 15 3.4 通信復(fù)雜度為O (nlogn)的算法 17 3.5 非基于比較的算法 20 3.5.1 時間片算法 20 3.5.2 變速算法 20 3.6 基于比較的算法的下界 22 3.7 非基于比較的算法的下界* 26 3.8 參考文獻(xiàn)注釋 27 3.9 習(xí)題 27 第4章 一般同步網(wǎng)絡(luò)中的算法 29 4.1 一般網(wǎng)絡(luò)中的領(lǐng)導(dǎo)者選舉 29 4.1.1 問題 29 4.1.2 簡單的洪泛算法 29 4.1.3 降低通信復(fù)雜度 31 4.2 廣度優(yōu)先搜索 32 4.2.1 問題 33 4.2.2 基本的廣度優(yōu)先搜索算法 33 4.2.3 應(yīng)用 34 4.3 短路徑 35 4.4 小生成樹 36 4.4.1 問題 36 4.4.2 基本定理 36 4.4.3 算法 38 4.5 獨立集 40 4.5.1 問題 40 4.5.2 隨機(jī)化算法 41 4.5.3 分析* 42 4.6 參考文獻(xiàn)注釋 44 4.7 習(xí)題 44 第5章 鏈路故障時的分布式 一致性 46 5.1 協(xié)同攻擊問題—確定性版本 46 5.2 協(xié)同攻擊問題—隨機(jī)化版本 48 5.2.1 形式化模型 49 5.2.2 算法 49 5.2.3 不一致的下限 52 5.3 參考文獻(xiàn)注釋 54 5.4 習(xí)題 54 第6章 進(jìn)程故障下的分布式 一致性 56 6.1 問題 57 6.2 針對停止故障的算法 58 6.2.1 基本算法 58 6.2.2 減少通信 60 6.2.3 指數(shù)信息收集算法 61 6.2.4 帶鑒別的Byzantine一致性 66 6.3 針對Byzantine故障的算法 66 6.3.1 舉例 67 6.3.2 Byzantine一致性問題的EIG 算法 68 6.3.3 使用二元Byzantine一致性的 一般Byzantine一致性問題 71 6.3.4 減少通信開銷 72 6.4 Byzantine一致性問題中進(jìn)程的 個數(shù) 75 6.5 一般圖中的Byzantine一致性 問題 78 6.6 弱Byzantine一致性 81 6.7 有停止故障時的輪數(shù) 82 6.8 參考文獻(xiàn)注釋 88 6.9 習(xí)題 89 第7章 更多的一致性問題 93 7.1 k一致性問題 93 7.1.1 問題 93 7.1.2 算法 94 7.1.3 下界* 95 7.2 近似一致性 103 7.3 提交問題 106 7.3.1 問題 106 7.3.2 兩階段提交 107 7.3.3 三階段提交 108 7.3.4 消息數(shù)的下界 110 7.4 參考文獻(xiàn)注釋 112 7.5 習(xí)題 112 第二部分 異步算法 第8章 建模II:異步系統(tǒng)模型 116 8.1 輸入/輸出自動機(jī) 116 8.2 自動機(jī)的操作 120 8.2.1 合成 120 8.2.2 隱藏 123 8.3 公平性 123 8.4 問題的輸入和輸出 126 8.5 屬性與證明方法 126 8.5.1 不變式斷言 126 8.5.2 軌跡屬性 126 8.5.3 安全與活性屬性 127 8.5.4 合成推理 129 8.5.5 層次化證明 131 8.6 復(fù)雜度衡量 133 8.7 不可區(qū)分的運行 134 8.8 隨機(jī)化 134 8.9 參考文獻(xiàn)注釋 134 8.10 習(xí)題 135 第二部分A?異步共享存儲器算法 第9章 建模III:異步共享存儲器 模型 138 9.1 共享存儲器系統(tǒng) 138 9.2 環(huán)境模型 140 9.3 不可區(qū)分狀態(tài) 141 9.4 共享變量類型 142 9.5 復(fù)雜度衡量 145 9.6 故障 146 9.7 隨機(jī)化 146 9.8 參考文獻(xiàn)注釋 146 9.9 習(xí)題 146 第10章 互斥 148 10.1 異步共享存儲器模型 148 10.2 問題 150 10.3 Dijkstra的互斥算法 153 10.3.1 算法 153 10.3.2 正確性證明 156 10.3.3 互斥條件的一個斷言式 證明 158 10.3.4 運行時間 159 10.4 互斥算法的更強(qiáng)條件 160 10.5 鎖定權(quán)互斥算法 162 10.5.1 雙進(jìn)程算法 162 10.5.2 n進(jìn)程算法 165 10.5.3 錦標(biāo)賽算法 169 10.6 使用單寫者共享寄存器的算法 172 10.7 Bakery算法 174 10.8 寄存器數(shù)量的下界 176 10.8.1 基本事實 177 10.8.2 單寫者共享變量 177 10.8.3 多寫者共享變量 178 10.9 使用讀–改–寫共享變量的 互斥 182 10.9.1 基本問題 182 10.9.2 有界繞過次數(shù) 183 10.9.3 鎖定權(quán) 188 10.9.4 模擬證明 190 10.10 參考文獻(xiàn)注釋 193 10.11 習(xí)題 193 第11章 資源分配 197 11.1?問題 197 11.1.1 顯式資源規(guī)格說明和互斥規(guī)格說明 197 11.1.2 資源分配問題 198 11.1.3 哲學(xué)家用餐問題 199 11.1.4 解法的受限形式 200 11.2 對稱哲學(xué)家用餐算法的 不存在性 200 11.3 右–左哲學(xué)家用餐算法 202 11.3.1 等待鏈 202 11.3.2 基本算法 203 11.3.3 擴(kuò)展 205 11.4 隨機(jī)哲學(xué)家用餐算法* 208 11.4.1 算法* 208 11.4.2 正確性* 210 11.5 參考文獻(xiàn)注釋 216 11.6 習(xí)題 216 第12章 一致性 218 12.1?問題 218 12.2 使用讀/寫共享存儲器的一致性 問題 220 12.2.1 限制 221 12.2.2 術(shù)語 221 12.2.3 雙價初始化 222 12.2.4 無等待終止性的不可能性 222 12.2.5 單故障終止性的不可能性 結(jié)果 224 12.3 讀/改/寫共享存儲器上的 一致性問題 227 12.4 其他共享存儲器類型 227 12.5 異步共享存儲器系統(tǒng)中的可 計算性* 227 12.6 參考文獻(xiàn)注釋 229 12.7 習(xí)題 229 第13章 原子對象 232 13.1 定義和基本結(jié)論 232 13.1.1 原子對象的定義 233 13.1.2 規(guī)范無等待原子對象 自動機(jī) 238 13.1.3 原子對象的合成 240 13.1.4 原子對象和共享變量 240 13.1.5 顯示原子性的一個充分 條件 245 13.2 用讀/寫變量實現(xiàn)讀–改–寫 原子對象 246 13.3 共享存儲器的原子快照 247 13.3.1 問題 247 13.3.2 帶無界變量的一個算法 248 13.3.3 帶有界變量的一個算法* 251 13.4 讀/寫原子對象 254 13.4.1 問題 254 13.4.2 證明原子性的其他引理 255 13.4.3 帶無界變量的一個算法 256 13.4.4 兩個寫者的有界算法 259 13.4.5 使用快照的算法 263 13.5 參考文獻(xiàn)注釋 264 13.6 習(xí)題 265 第二部分B 異步網(wǎng)絡(luò)算法 第14章 建模IV:異步網(wǎng)絡(luò)模型 268 14.1 發(fā)送/接收系統(tǒng) 268 14.1.1 進(jìn)程 268 14.1.2 發(fā)送/接收通道 269 14.1.3 異步發(fā)送/接收系統(tǒng) 272 14.1.4 使用可靠FIFO通道的發(fā)送/ 接收系統(tǒng)的屬性 272 14.1.5 復(fù)雜度度量 273 14.2 廣播系統(tǒng) 274 14.2.1 進(jìn)程 274 14.2.2 廣播通道 274 14.2.3 異步廣播系統(tǒng) 275 14.2.4 采用可靠廣播通道的廣播系統(tǒng)的屬性 275 14.2.5 復(fù)雜度度量 275 14.3 多播系統(tǒng) 275 14.3.1 進(jìn)程 276 14.3.2 多播通道 276 14.3.3 異步多播系統(tǒng) 276 14.4 參考文獻(xiàn)注釋 277 14.5 習(xí)題 277 第15章 基本異步網(wǎng)絡(luò)算法 279 15.1 環(huán)中的領(lǐng)導(dǎo)者選舉 279 15.1.1 LCR算法 279 15.1.2 HS算法 283 15.1.3 PetersonLeader算法 283 15.1.4 通信復(fù)雜度的下界 286 15.2 任意網(wǎng)絡(luò)中的領(lǐng)導(dǎo)者選舉 291 15.3 生成樹的構(gòu)造、廣播和斂播 292 15.4 廣度優(yōu)先搜索和短路徑 295 15.5 小生成樹 300 15.5.1 問題描述 301 15.5.2 同步算法:回顧 301 15.5.3 GHS算法:概要 302 15.5.4 更詳細(xì)的算法 303 15.5.5 特殊消息 305 15.5.6 復(fù)雜度分析 306 15.5.7 GHS算法的正確性證明 307 15.5.8 簡單“同步”策略 308 15.5.9 應(yīng)用到領(lǐng)導(dǎo)者選舉算法中 308 15.6 參考文獻(xiàn)注釋 309 15.7 習(xí)題 309 第16章 同步器 313 16.1 問題 313 16.2 局部同步器 315 16.3 安全同步器 319 16.3.1 前端自動機(jī) 320 16.3.2 通道自動機(jī) 321 16.3.3 安全同步器的任務(wù) 321 16.3.4 正確性 322 16.4 安全同步器的實現(xiàn) 322 16.4.1 同步器Alpha 322 16.4.2 同步器Beta 323 16.4.3 同步器Gamma 323 16.5 應(yīng)用 327 16.5.1 領(lǐng)導(dǎo)者選舉 327 16.5.2 廣度優(yōu)先搜索 327 16.5.3 短路徑 328 16.5.4 廣播與確認(rèn) 328 16.5.5 獨立集 328 16.6 時間下界 328 16.7 參考文獻(xiàn)注釋 331 16.8 習(xí)題 331 第17章 共享存儲器與網(wǎng)絡(luò) 333 17.1 從異步共享存儲器模型到異步 網(wǎng)絡(luò)模型的轉(zhuǎn)換 333 17.1.1 問題 333 17.1.2 無故障時的策略 334 17.1.3 容忍進(jìn)程故障的算法 339 17.1.4 對于n/2故障的不可能性 結(jié)果 342 17.2 從異步網(wǎng)絡(luò)模型到異步共享存儲器模型的轉(zhuǎn)換 343 17.2.1 發(fā)送/接收系統(tǒng) 344 17.2.2 廣播系統(tǒng) 345 17.2.3 異步網(wǎng)絡(luò)中一致性的 不可能性 346 17.3 參考文獻(xiàn)注釋 346 17.4 習(xí)題 346 第18章
你還可能感興趣
我要評論
|