前　　言
Distributed Algorithms
分布式算法是用于解決多個(gè)互連處理器運(yùn)行問題的算法。分布式算法的各部分并發(fā)和獨(dú)立地運(yùn)行，每一部分只承載有限的信息。即使處理器和通信信道以不同的速度運(yùn)作，或即使某些構(gòu)件出了故障，這些算法仍然應(yīng)該正常運(yùn)行。
分布式算法有廣泛的應(yīng)用：電信、分布式信息處理、科學(xué)計(jì)算以及實(shí)時(shí)進(jìn)程控制。例如，電話系統(tǒng)、航班訂票系統(tǒng)、銀行系統(tǒng)、全球信息系統(tǒng)、天氣預(yù)報(bào)系統(tǒng)以及飛機(jī)和核電站控制系統(tǒng)都嚴(yán)重依賴于分布式算法。很明顯，確保分布式算法準(zhǔn)確、高效地運(yùn)行是非常重要的。然而，由于這種算法的執(zhí)行環(huán)境很復(fù)雜，所以設(shè)計(jì)分布式算法就成了一項(xiàng)困難的
任務(wù)。
本書對(duì)分布式算法這個(gè)領(lǐng)域做了全面的介紹，包括為重要的算法和不可能性結(jié)果，且都在一種簡單的自動(dòng)機(jī)理論環(huán)境中呈現(xiàn)。幾乎所有的解都附有數(shù)學(xué)證明（至少是粗略的）。每個(gè)算法都根據(jù)精確定義的復(fù)雜度衡量方法進(jìn)行了分析�？傊�，這些內(nèi)容為更深入地理解分布式算法打下了牢固的基礎(chǔ)。
本書面向不同層次的讀者。首先，本書可以作為計(jì)算機(jī)系一年級(jí)研究生的教材，尤其適合于對(duì)計(jì)算機(jī)系統(tǒng)、理論或兩者懷有濃厚興趣的學(xué)生學(xué)習(xí)。其次，本書可作為分布式系統(tǒng)設(shè)計(jì)人員的短期培訓(xùn)教材。后，它也可作為參考手冊(cè)，供設(shè)計(jì)人員、學(xué)生、研究人員以及任何對(duì)該領(lǐng)域感興趣的人使用。
本書包含了針對(duì)很多典型問題的算法，如在幾種不同系統(tǒng)環(huán)境下的一致性（consensus）、通信、資源分配和同步問題。這些算法和相應(yīng)結(jié)果基于分布式環(huán)境的基本假設(shè)來組織。組織的層基于時(shí)序模型（timing model）—同步、異步或部分同步；第二層基于進(jìn)程間的通信機(jī)制—共享存儲(chǔ)器或消息傳遞。每種系統(tǒng)模型都用數(shù)章來闡述：每一部分的頭一章提出所述系統(tǒng)類型的形式化模型，余下各章介紹算法和不可能性結(jié)果。從頭至尾，本書進(jìn)行了嚴(yán)密的論述，然而非常簡明易懂。
由于該領(lǐng)域很廣闊，變化也很快，因此本書并不包羅萬象，只包括根本的結(jié)果。若以復(fù)雜度來衡量，這些結(jié)果并不總是的，但它們比較簡單且能夠闡明重要的通用設(shè)計(jì)和推理方法。
本書將會(huì)介紹分布式計(jì)算領(lǐng)域中許多重要的問題、算法和不可能性結(jié)果。當(dāng)實(shí)際系統(tǒng)中出現(xiàn)這些問題的時(shí)候，你就能將它們識(shí)別出來，并進(jìn)而利用本書介紹的算法來解決它們，或者應(yīng)用不可能性結(jié)果來證明它們是不可解的。本書還介紹各類系統(tǒng)模型及其能力。這樣一來，你自己就可以設(shè)計(jì)出新算法（甚至還可以證明出新的不可能性結(jié)果）。后，本書還會(huì)讓你相信，嚴(yán)格推導(dǎo)分布式算法和系統(tǒng)是可行的：形式化建模，給出其所需行為的精確規(guī)格說明，嚴(yán)格證明它們符合規(guī)格說明，確定合適的復(fù)雜度衡量標(biāo)準(zhǔn)以及按照這些標(biāo)準(zhǔn)進(jìn)行分析。
使用本書
預(yù)備知識(shí)　閱讀本書需要對(duì)基本的本科離散數(shù)學(xué)（包括數(shù)學(xué)歸納和漸近分析）、一些編程技能以及計(jì)算機(jī)系統(tǒng)相當(dāng)熟悉。有關(guān)隨機(jī)算法的部分還需要基本的概率知識(shí)。有關(guān)串行算法及其分析的本科課程對(duì)閱讀本書有幫助，但并不是必要的。
章節(jié)關(guān)系　本書的編排原則是使讀者能比較獨(dú)立地閱讀不同模型的各章內(nèi)容。各章之間的依賴關(guān)系如圖A所示。例如，如果想盡快了解異步網(wǎng)絡(luò)，就可以跳過第5～7章。還可以只讀算法部分，而不必先閱讀算法所依賴的建模部分。

圖A　各章之間的依賴關(guān)系
帶星號(hào)的小節(jié)　在本書中，有幾個(gè)小節(jié)的標(biāo)題打了星號(hào)。它們的內(nèi)容不太基本或者說比其他部分更深。次閱讀的時(shí)候可以忽略這些內(nèi)容而不會(huì)有什么影響。
課程　本書的第1版已經(jīng)在MIT（麻省理工學(xué)院）的研究生導(dǎo)論課中用了很多年，并且在一些計(jì)算機(jī)軟件和應(yīng)用公司的系統(tǒng)設(shè)計(jì)師夏季課程中用了三年。本書包括足夠一年課程的內(nèi)容，所以對(duì)一些短期課程來說必須有所取舍（注意看章節(jié)之間的關(guān)系）。
例如，在學(xué)習(xí)異步網(wǎng)絡(luò)計(jì)算的一個(gè)學(xué)期的課程中，可以選擇第3、4、6章，7.2節(jié)，第12章和第14～21章，參考一些有關(guān)建模的章節(jié)（第2、8和9章），并根據(jù)需要加入第10、11和13章中的一些定義。在學(xué)習(xí)分布一致性的一個(gè)學(xué)期的課程中，可以選擇第2～9章、第12章、13.1節(jié)，以及第15、17、21、23和25章。還有其他多種可能組合。如果你是這個(gè)領(lǐng)域的研究者，你可以用所在領(lǐng)域的更新或者更特別的研究結(jié)果來補(bǔ)充本書。
在為系統(tǒng)設(shè)計(jì)師提供的一兩周的短期課程中，可以突出所有章節(jié)的重點(diǎn)，在較高的層次上討論關(guān)鍵結(jié)果和關(guān)鍵證明思想，而無須講解太多細(xì)節(jié)。
錯(cuò)誤　如果在本書中發(fā)現(xiàn)了錯(cuò)誤，或者對(duì)本書有什么建設(shè)性建議，請(qǐng)告訴我。特別歡迎對(duì)額外問題的建議。請(qǐng)發(fā)送email到distalgs@theory.lcs.mit.edu。
致謝
我很難一一列舉出所有對(duì)本書的出版做出貢獻(xiàn)的人們，因?yàn)楸緯�是多年教學(xué)和研究的成果，得到了許多學(xué)生和研究人員的幫助。即使這樣，我還是想盡力而為。
本書是MIT的研究生課程6.852（分布式算法）講稿的終版本。在我早期組織素材的過程中，學(xué)生們學(xué)過這門課。這些學(xué)生在1990年和1992年幫助我完成了講稿的在線版本。有幾位課程助教對(duì)我整理筆記給予了極大的幫助，他們是Ken Goldman、Isaac Saias和Boaz Patt-Shamir。助教Jennifer Welch 和Rainer Gawlick也幫了我很大的忙。
許多同事和學(xué)生與我一起研究過本書中的一些結(jié)果，與我一起討論了其他人的工作，這對(duì)我充分理解素材幫助很大。其中包括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就與我一起致力于研究這個(gè)當(dāng)時(shí)還很小但看起來很有前途的領(lǐng)域，而Mark Tuttle的碩士論文定義并發(fā)展了I/O自動(dòng)機(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)槲野才帕藢憰�的時(shí)間。Morgan Kaufmann的Bruce Spatz又一次鼓勵(lì)并幫助我做這個(gè)艱巨的工作，他總能給我正確的建議。在本書后付梓階段，Morgan Kaufmann的Julie Pabst和Diane Cerra給了我很大幫助。同時(shí)，也感謝Babel出版社的Ed Sznyter的LATEX技術(shù)。
后也是重要的，我要感謝體貼我的家人Dennis、Patrick和Mary Lynch，他們體諒我為本書所做的一切工作，同時(shí)幫我處理了其他的事情。特別感謝Dennis，當(dāng)我把大部分時(shí)間花在計(jì)算機(jī)前時(shí)，Dennis在為我準(zhǔn)備美味的海鮮晚餐，甚至把我的浴室和洗衣房翻修
一新！

Nancy A. Lynch
Cambridge, Massachusetts