分布式計算

內(nèi)容概要

　　分布式計算是指由計算機(jī)網(wǎng)絡(luò)連接的多處理平臺的各種形式的計算、信息訪問與信息交換。《分布式計算：原理、算法與系統(tǒng)》覆蓋了分布式計算中的理論、算法以及系統(tǒng)方面的基本原理和模型。兼顧理論的廣度與深度，注重實際，包括了互斥、死鎖檢測、認(rèn)證和失效恢復(fù)等常見問題。算法經(jīng)過認(rèn)真選擇，描述清晰，使用簡單的解釋和圖表來說明算法。對于有重大影響的新興主題，例如P2P網(wǎng)絡(luò)和網(wǎng)絡(luò)安全，也包括在本書中?！　　斗植际接嬎悖涸怼⑺惴ㄅc系統(tǒng)》涵蓋了最新的算法、大量的圖解以及豐富的示例和習(xí)題，將有助于電子與計算機(jī)工程和計算機(jī)科學(xué)等專業(yè)研究生學(xué)習(xí)該課程，數(shù)據(jù)網(wǎng)絡(luò)及傳感器網(wǎng)絡(luò)等方面的科研丁作者也可參考使用。

作者簡介

作者：（美國）克謝姆卡亞尼（Ajay D.Kshemkalyani） （美國）辛哈（Mukesh Singhal） 譯者：余宏亮 張冬艷  克謝姆卡亞尼，伊利諾伊大學(xué)計算機(jī)科學(xué)系副教授。1991年獲俄亥俄州立大學(xué)計算機(jī)與信息科學(xué)博士學(xué)位，1999年獲得美國國家科學(xué)基金會的CAREER獎。IEEE高級會員。研究領(lǐng)域包括分布式計算、算法、計算機(jī)網(wǎng)絡(luò)和并行系統(tǒng)?，F(xiàn)任Computer Networks編輯委員會委員。 辛哈，肯塔基大學(xué)計算機(jī)科學(xué)系教授，Gartner Group Endowed主席。1986年獲馬里蘭大學(xué)計算機(jī)科學(xué)博士學(xué)位。IEEEFellow，于2003年獲IEEE技術(shù)成就獎?，F(xiàn)任IEEE Transactions on Parallel and Distributed Systems及IEEE Transactions on Computers編輯委員會委員。研究領(lǐng)域包括分布式系統(tǒng)、計算機(jī)網(wǎng)絡(luò)、無線及移動計算系統(tǒng)、性能評價和計算機(jī)安全等。

書籍目錄

第一章引言 1.1定義 1.2與計算機(jī)系統(tǒng)部件的關(guān)系 1.3動機(jī) 1.4與并行多處理器／多計算機(jī)系統(tǒng)的關(guān)系 1.4.1并行系統(tǒng)的特性 1.4.2 Flynn的分類法 1.4.3耦合、并行、并發(fā)及粒度 1.5 消息傳遞系統(tǒng)與共享內(nèi)存系統(tǒng)的對比 1.5.1在共享內(nèi)存的系統(tǒng)上仿真消息傳遞 1.5.2在消息傳遞系統(tǒng)上仿真共享內(nèi)存 1.6分布式通信的原語 1.6.1阻塞／非阻塞，同步／異步原語  1.6.2處理器同步性 1.6.3庫與標(biāo)準(zhǔn) 1.7同步與異步執(zhí)行 1.7.1通過同步系統(tǒng)仿真異步系統(tǒng) 1.7.2通過異步系統(tǒng)仿真同步系統(tǒng) 1.7.3仿真 1.8設(shè)計主題與挑戰(zhàn) 1.8.1從系統(tǒng)角度看分布式系統(tǒng)的挑戰(zhàn) 1.8.2分布式計算中的算法挑戰(zhàn) 1.8.3分布式計算的應(yīng)用以及更新的挑戰(zhàn) 1.9關(guān)于主題的選擇與覆蓋 1.10本章小結(jié) 1.11習(xí)題 1.12參考文獻(xiàn)說明 參考文獻(xiàn) 第二章分布式計算模型 2.1分布式程序 2.2分布式運(yùn)行模型 2.3通信網(wǎng)絡(luò)模型 2.4分布式系統(tǒng)的全局狀態(tài) 2.4.1全局狀態(tài) 2.5分布式計算的運(yùn)行分割 2.6事件的過去和未來錐面 2.7進(jìn)程通信模型 2.8本章小結(jié) 2.9習(xí)題 2.10參考文獻(xiàn)說明 參考文獻(xiàn) 第三章邏輯時間 3.1引言 3.2邏輯時鐘框架 3.2.1定義 3.2.2實現(xiàn)邏輯時鐘 3.3標(biāo)量時間 3.3.1定義 3.3.2基本性質(zhì) 3.4向量時間 3.4.1定義 3.4.2基本性質(zhì) 3.4.3有關(guān)向量時鐘的大小  3.5向量時鐘的有效實現(xiàn) 3.5.1 Singhal-Kshemkalyani的差量技術(shù) 3.5.2 Fowler-Zwaenepoel的直接依賴技術(shù) 3.6 Jard-Jourdan的自適應(yīng)技術(shù) 3.7矩陣時間 3.7.1定義 3.7.2基本性質(zhì) 3.8虛擬時間 3.8.1虛擬時間的定義 3.8.2與Lamport邏輯時鐘比較 3.8.3時間變形機(jī)制 3.8.4本地控制機(jī)制 3.8.5全局控制機(jī)制 3.9物理時鐘同步：NTP 3.9.1動機(jī) 3.9.2定義及術(shù)語 3.9.3時鐘不準(zhǔn)確性 3.10本章小結(jié) 3.11習(xí)題 3.12參考文獻(xiàn)說明 參考文獻(xiàn) 第四章記錄全局狀態(tài)與快照算法 4.1引言 4.2系統(tǒng)模型和定義 4.2.1系統(tǒng)模型 4.2.2一致性全局狀態(tài) 4.2.3有關(guān)分割的解 4.2.4記錄全局快照時遇到的問題 4.3 FIFO通道的快照算法 4.3.1 Chandy-Lamport算法 4.3.2被記錄全局狀態(tài)的性質(zhì) 4.4 Chandy-Lamport算法的變種 4.4.1 Spezialetti-Kearns算法 4.4.2 Venkatesan快照增量算法 4.4.3 Helary波同步方法 4.5非FIFO通道的快照算法 4.5.1 Lai-Yang算法 4.5.2 Li等人的算法 4.5.3 Mattern算法 4.6因果傳遞系統(tǒng)快照 4.6.1進(jìn)程狀態(tài)記錄 4.6.2 Acharya-Badrinath算法中的通道狀態(tài)記錄 4.6.3 Alagar-Venkatesan算法中的通道狀態(tài)記錄  4.7監(jiān)控全局狀態(tài) 4.8一致性全局快照的必要和充分條件 4.8.1 Zigzag路徑和一致性全局快照 4.9找出分布式計算中的一致性全局快照 4.9.1找出一致性全局快照  4.9.2枚舉式一致性快照Manivannan-Netzer-Singhal算法 4.9.3在分布式計算中找出Z路徑 4.10本章小結(jié) 4.11習(xí)題 4.12參考文獻(xiàn)說明 參考文獻(xiàn) 第五章術(shù)語和基本算法 5.1拓?fù)涑橄蠛透采w 5.2分類和基本概念 5.2.1應(yīng)用執(zhí)行和控制算法執(zhí)行 5.2.2集中式算法和分布式算法 5.2.3對稱算法和非對稱算法 5.2.4匿名算法 5.2.5一致算法 5.2.6自適應(yīng)算法 5.2.7確定性執(zhí)行對非確定性執(zhí)行  5.2.8執(zhí)行抑制 5.2.9同步系統(tǒng)和異步系統(tǒng) 5.2.10聯(lián)機(jī)算法與脫機(jī)算法 5.2.11故障模型 5.2.12無需等待算法 5.2.13通信通道 5.3復(fù)雜度測量和度量 5.4程序結(jié)構(gòu) 5.5圖的基本算法 5.5.1使用洪泛法的同步單一啟動者生成樹算法 5.5.2使用洪泛法的異步單一啟動者生成樹算法 5.5.3使用洪泛法的異步并發(fā)啟動者生成樹算法 …… 第六章消息序與組通信 第七章終止檢測 第八章知識推理 第九章分布式互斥算法 第十章死鎖檢測 第十一章全局謂詞的檢測 第十二章分布式共享內(nèi)存 第十三章檢查點(diǎn)和卷回恢復(fù) 第十四章共識和協(xié)定算法 第十五章失效檢測 第十六章分布式系統(tǒng)中的驗證 第十七章自穩(wěn)定 第十八章對等計算及覆蓋網(wǎng)絡(luò)

章節(jié)摘錄

版權(quán)頁：   插圖：   3.8.3 時間變形機(jī)制 在使用時間變形機(jī)制實現(xiàn)虛擬時間時，消息的虛擬接收事件被認(rèn)為是其時間戳。虛擬時間正確實現(xiàn)的充分和必要條件是每個進(jìn)程必須按時間戳次序處理輸入的信息，因處理的速度和消息延遲的變數(shù)很大，故該條件的限制非常嚴(yán)格也很不理想。所以有些進(jìn)程在虛擬時間上快于其他進(jìn)程也是很自然的。 因為我們假定虛擬時間是實數(shù)，所以一個進(jìn)程僅憑本地信息就阻塞并等待帶有下一個時間戳的消息是不可能的。帶有較早時間戳的消息遲到的可能性也總是存在。這樣，當(dāng)進(jìn)程執(zhí)行一個消息時，確定帶有較早時間戳的消息是否會遲到是非常困難的。這就是時間變形機(jī)制將要解決的虛擬時問的中心問題。 時間變形機(jī)制的優(yōu)點(diǎn)是它具有不依賴于下層計算機(jī)結(jié)構(gòu)且很容易實現(xiàn)于不同系統(tǒng)的可移植性?？傊⑼ㄐ疟徽J(rèn)為是可靠的，但消息的傳送可能不按FIFO次序進(jìn)行。 時間變形機(jī)制由兩部分組成：本地控制機(jī)制和全局控制機(jī)制。本地控制機(jī)制保證按正確的次序執(zhí)行事件和處理消息；全局控制機(jī)制處理全局進(jìn)展、終止檢測、I／O錯誤處理及流控制等全局問題。 3.8.4 本地控制機(jī)制 在本地控制機(jī)制的實現(xiàn)過程中，不存在全局時鐘變量。每個進(jìn)程有一個本地時鐘，一個進(jìn)程的本地虛擬時鐘在該進(jìn)程上的一個事件存在期間不發(fā)生變化，僅在兩個事件之間改變。在處理來自輸入隊列的下一消息時，進(jìn)程把它的時鐘增加到這個消息的時間戳的值。在任一瞬間，每個進(jìn)程的虛擬時間值可能不同，但該值對系統(tǒng)中其他進(jìn)程是透明的。 當(dāng)一個消息被發(fā)送時，拷貝發(fā)送方的時鐘為虛擬發(fā)送時間，而接收方的名稱和虛擬接收時間根據(jù)應(yīng)用特定的上下文賦值。 在一個進(jìn)程上的所有到達(dá)消息按時間戳（收到時間）增序存儲在輸入隊列中。理想的情況是應(yīng)當(dāng)沒有過去（稱為遲到的消息）的消息到達(dá)一個進(jìn)程。然而，由于進(jìn)程不同的計算速度以及網(wǎng)絡(luò)延遲等因素，進(jìn)程會接收到遲到的消息。虛擬時間的語義要求輸入消息嚴(yán)格按時間戳次序被每個進(jìn)程接收。實現(xiàn)該要求的唯一方法是：在收到一個遲到的消息時，接受者回滾到較早的一個虛擬時間，撤銷其間所產(chǎn)生的一切附帶的影響，然后通過以合適的順序執(zhí)行這個遲到的消息并再次向前執(zhí)行。

媒體關(guān)注與評論

　　“本書比較適合于進(jìn)行分布式系統(tǒng)的教學(xué)以及加深相關(guān)工程人員對分布式系統(tǒng)原理的理解。由于現(xiàn)在市面上有關(guān)分布式算法方面的書還很少，而與系統(tǒng)相結(jié)合方面就更少了。因此，建議翻譯本書，方便相關(guān)的學(xué)生、研究人員與工程技術(shù)人面參考。”　　——清華大學(xué) 鄭緯民

編輯推薦

《分布式計算:原理、算法與系統(tǒng)》涵蓋了最新的算法、大量的圖解以及豐富的示例和習(xí)題，將有助于電子與計算機(jī)工程和計算機(jī)科學(xué)等專業(yè)研究生學(xué)習(xí)該課程，數(shù)據(jù)網(wǎng)絡(luò)及傳感器網(wǎng)絡(luò)等方面的科研工作者也可參考使用。

名人推薦

“本書比較適合于進(jìn)行分布式系統(tǒng)的教學(xué)以及加深相關(guān)工程人員對分布式系統(tǒng)原理的理解。由于現(xiàn)在市面上有關(guān)分布式算法方面的書還很少，而與系統(tǒng)相結(jié)合方面的就更少了。因此，建議翻譯本書，方便相關(guān)的學(xué)生、研究人員與工程技術(shù)人員參考?！?--清華大學(xué) 鄭緯民

圖書封面

圖書標(biāo)簽Tags

無

評論、評分、閱讀與下載

---

    分布式計算 PDF格式下載

---