分布式系統(tǒng)中的計算模型

1、1第第4章章分布式系統(tǒng)中的計算模型分布式系統(tǒng)中的計算模型2006.12.152概述概述n分布式系統(tǒng)計算模型的復雜性分布式系統(tǒng)計算模型的復雜性v系統(tǒng)由并發(fā)執(zhí)行部件構(gòu)成系統(tǒng)由并發(fā)執(zhí)行部件構(gòu)成v系統(tǒng)中無全局時鐘系統(tǒng)中無全局時鐘v必須捕捉系統(tǒng)部件可能的失效必須捕捉系統(tǒng)部件可能的失效n對策對策v因果關(guān)系（因果關(guān)系（Causality）v一致狀態(tài)（一致狀態(tài)（Consistent states）v全局狀態(tài)全局狀態(tài)34.1 基本知識基本知識n 協(xié)議（協(xié)議（Protocol）n 協(xié)議中的控制語句協(xié)議中的控制語句 1.Send（destination, action; parameters） destinatio

2、n：處理器抽象。實用中是通信實體的地址：處理器抽象。實用中是通信實體的地址： 機器名，機器的端口號機器名，機器的端口號(即即1個個socket地址地址) action： 控制控制msg，希望接收者采取的動作，希望接收者采取的動作 parameters：參數(shù)集合參數(shù)集合 假定：假定： msg發(fā)送是無阻塞、可靠的（語義類似于發(fā)送是無阻塞、可靠的（語義類似于TCP套接字）；套接字）； 有時假定較弱的有時假定較弱的msg傳遞層（等價于傳遞層（等價于UDP）。）。TCP與與UDP的區(qū)別：的區(qū)別：基于連接與無連接基于連接與無連接對系統(tǒng)資源的要求（對系統(tǒng)資源的要求（TCP較多，較多，UDP少）少） UDP程

3、序結(jié)構(gòu)較簡單程序結(jié)構(gòu)較簡單流模式與數(shù)據(jù)報模式流模式與數(shù)據(jù)報模式 TCP保證數(shù)據(jù)正確性，保證數(shù)據(jù)正確性，UDP可能丟包可能丟包 TCP保證數(shù)據(jù)順序，保證數(shù)據(jù)順序，UDP不保證不保證44.1 基本知識基本知識2.接收接收msg 接收接收msg可推廣至接收事件，引起事件的原因是：可推廣至接收事件，引起事件的原因是： 外部外部msg、超時設(shè)定、內(nèi)部中斷、超時設(shè)定、內(nèi)部中斷 事件在處理前，一般是在緩沖區(qū)事件在處理前，一般是在緩沖區(qū)(如事件隊列如事件隊列)中，若一處理中，若一處理器想處理事件，它必須執(zhí)行一個聲明處理這些事件的線程。器想處理事件，它必須執(zhí)行一個聲明處理這些事件的線程。 例如，一個節(jié)點通過執(zhí)行

4、下述代碼等待事件例如，一個節(jié)點通過執(zhí)行下述代碼等待事件A1, A2,., An waiting for A1, A2,., An ：/聲明聲明 A1（Source; parameters） Code to handle A1 . An（Source; parameters） Code to handle An 當當p執(zhí)行執(zhí)行send(q, A1; parameters)且且q執(zhí)行上述代碼時，執(zhí)行上述代碼時，q將將最終處理由最終處理由p發(fā)送的發(fā)送的msg54.1 基本知識基本知識3.超時超時 當懷疑遠程處理器失效時，可通過超時檢測來判定：當懷疑遠程處理器失效時，可通過超時檢測來判定：當當T秒后仍

5、未收到秒后仍未收到P的類型為的類型為event的的msg時，執(zhí)行指定的動作時，執(zhí)行指定的動作 waiting until P sends (event; parameters), timeout=T on timeout timeout action僅當收到一個響應僅當收到一個響應msg時才采取動作，超時不做任何動作時才采取動作，超時不做任何動作 waiting until P sends (event; parameters), timeout=T on timeout； if no timeout occurred Successful response actions 64.1 基本知識

6、基本知識3.超時超時處理器等待響應處理器等待響應T T秒秒 若處理器在等待開始后若處理器在等待開始后T T秒內(nèi)沒響應，則等待結(jié)束，協(xié)議繼續(xù)秒內(nèi)沒響應，則等待結(jié)束，協(xié)議繼續(xù) waiting up to T seconds for (event; parameters) msgs Event: 74.2 因果關(guān)系因果關(guān)系 分布式系統(tǒng)為何缺乏全局的系統(tǒng)狀態(tài)？分布式系統(tǒng)為何缺乏全局的系統(tǒng)狀態(tài)？ 1.非即時通信非即時通信 A A和和B B同時向?qū)Ψ胶霸捦瑫r向?qū)Ψ胶霸?他們都認為是自己先喊話他們都認為是自己先喊話 C C聽到兩人是同時喊話聽到兩人是同時喊話 結(jié)論：結(jié)論：系統(tǒng)的全局狀態(tài)依賴于觀察點系統(tǒng)的全局

7、狀態(tài)依賴于觀察點 原因：原因： 傳播延遲傳播延遲 網(wǎng)絡(luò)資源的競爭網(wǎng)絡(luò)資源的競爭 丟失丟失msg重發(fā)重發(fā) ACBd1 = d284.2 因果關(guān)系因果關(guān)系2.相對性影響相對性影響 假設(shè)張三和李四決定使用同步時鐘來觀察全局狀態(tài)：假設(shè)張三和李四決定使用同步時鐘來觀察全局狀態(tài)： 他們約定下午他們約定下午5 5點在某餐館會面，張三準時到達，但李四點在某餐館會面，張三準時到達，但李四在一個接近在一個接近光速的日光系統(tǒng)光速的日光系統(tǒng)中游覽。中游覽。 張三在等待李四張三在等待李四1 1小時后離開餐館，而李四在自己的表到小時后離開餐館，而李四在自己的表到達達5 5點時準時達到餐館，但他認為張三未達到。點時準時達到

8、餐館，但他認為張三未達到。 因為大多數(shù)計算機的實際時鐘均存在漂移，故相對速度不因為大多數(shù)計算機的實際時鐘均存在漂移，故相對速度不同，時鐘同步仍然是一個問題。同，時鐘同步仍然是一個問題。 結(jié)論：結(jié)論：使用時間來同步不是一個可靠機制。使用時間來同步不是一個可靠機制。94.2 因果關(guān)系因果關(guān)系3.中斷中斷 假設(shè)張三和李四在同一起跑線上賽跑，信號為小旗，前兩假設(shè)張三和李四在同一起跑線上賽跑，信號為小旗，前兩個問題可以忽略，但是個問題可以忽略，但是 即使可忽略其他影響，也不可能指望不同的機器會同時做即使可忽略其他影響，也不可能指望不同的機器會同時做出某些反應。因為現(xiàn)代計算機是一個很復雜的系統(tǒng)：出某些反應

9、。因為現(xiàn)代計算機是一個很復雜的系統(tǒng)：CPUCPU競爭、中斷、頁錯誤等，執(zhí)行時間無法預料。競爭、中斷、頁錯誤等，執(zhí)行時間無法預料。結(jié)論：結(jié)論：不可能在同一時刻觀察一個分布式系統(tǒng)的全局狀態(tài)不可能在同一時刻觀察一個分布式系統(tǒng)的全局狀態(tài) 必須找到某種可以依賴的性質(zhì)：必須找到某種可以依賴的性質(zhì)：時間回溯時間回溯因果相關(guān)因果相關(guān)104.2 因果關(guān)系因果關(guān)系n 假設(shè)分布式系統(tǒng)構(gòu)成：假設(shè)分布式系統(tǒng)構(gòu)成： P PPP1 1, P, P2 2,., P,., Pn n ：處理器集合：處理器集合 E E：全體事件的集合：全體事件的集合 E Ep pE E, , E Ep p表示發(fā)生在表示發(fā)生在p p上的所有事件上的

10、所有事件n 次序次序 e e1 1ee2 2： 事件事件e e1 1發(fā)生發(fā)生e e2 2在之前（亦記：在之前（亦記：e e1 1ee2 2） e e1 1 I e e2 2：事件：事件e e1 1發(fā)生發(fā)生e e2 2在之前，在之前，I為信息源為信息源n 定序定序 有些有些E E中事件很容易定序：中事件很容易定序：v 發(fā)生在同一節(jié)點發(fā)生在同一節(jié)點p p上的事件滿足全序：上的事件滿足全序： 若若e e1 1,e,e2 2 E Ep p，則，則 e e1 1 pe e2 2 或或 e e2 2 pe e1 1 成立成立ve e1 1發(fā)送消息發(fā)送消息m,em,e2 2接收接收m m，則，則e e1 1

11、 me e2 2114.2 因果關(guān)系因果關(guān)系n Happens-before關(guān)系（關(guān)系（ H） 該關(guān)系是節(jié)點次序和消息傳遞次序的傳遞閉包該關(guān)系是節(jié)點次序和消息傳遞次序的傳遞閉包：v規(guī)則規(guī)則1 1：若若e e1 1 pe e2 2，則，則e e1 1 He e2 2v規(guī)則規(guī)則2 2：若若e e1 1 me e2 2，則，則e e1 1 He e2 2v規(guī)則規(guī)則3 3：若若e e1 1 He e2 2，且，且e e2 2 He e3 3，則，則e e1 1 He e3 3 e e1 1 He e3 3表示存在表示存在1 1個事件因果鏈，使個事件因果鏈，使e e1 1發(fā)生發(fā)生e e3 3在之前在之前

12、 Note: Note: H是一種偏序關(guān)系，即是一種偏序關(guān)系，即 存在存在e e和和ee，二者之間無這種關(guān)系，二者之間無這種關(guān)系v并發(fā)事件：并發(fā)事件：若兩事件不能由若兩事件不能由 H定序定序 在集合在集合 X 上的二元關(guān)系上的二元關(guān)系 R 的傳遞閉包是包含的傳遞閉包是包含 R 的的 X 上的最小的傳遞關(guān)系。上的最小的傳遞關(guān)系。 124.2 因果關(guān)系因果關(guān)系nHappens-before關(guān)系（關(guān)系（ H）v規(guī)則規(guī)則1 1表述的是同一處理器上兩個事件之間的因果關(guān)系；表述的是同一處理器上兩個事件之間的因果關(guān)系；v規(guī)則規(guī)則2 2表述了不同處理器上兩個事件之間的因果關(guān)系表述了不同處理器上兩個事件之間的因

13、果關(guān)系v規(guī)則規(guī)則3 3闡述了傳遞律闡述了傳遞律Note: Happens-Before關(guān)系完整表述了執(zhí)行中的因果關(guān)系。關(guān)系完整表述了執(zhí)行中的因果關(guān)系。如果一個執(zhí)行中的事件按照其相對順序重新進行排如果一個執(zhí)行中的事件按照其相對順序重新進行排序，而不改變他們的序，而不改變他們的happens-before關(guān)系的話，那關(guān)系的話，那么其結(jié)果仍是一個執(zhí)行，并且對處理器而言，該執(zhí)么其結(jié)果仍是一個執(zhí)行，并且對處理器而言，該執(zhí)行與原執(zhí)行并無區(qū)別。行與原執(zhí)行并無區(qū)別。134.2 因果關(guān)系因果關(guān)系n 舉例舉例1)1)因事件因事件e1,e4e1,e4和和e7e7均發(fā)生在均發(fā)生在P1P1上，故：上，故：e e1 1

14、P1e e4 4 P1e e7 72)2)因因e1e1發(fā)送發(fā)送1 1個個msgmsg到到e3e3，故：，故：e e1 1 me e3 3，類似地，類似地e e5 5 me e8 83)3)應用規(guī)則應用規(guī)則1 1和和2 2得：得： e e1 1 He e4 4 He e7 7，e e1 1 He e3 3，e e5 5 He e8 84)4)由由 H的傳遞閉包性質(zhì)得：的傳遞閉包性質(zhì)得： e e1 1 He e8 85)e15)e1和和e6e6是并發(fā)的：是并發(fā)的：e1e1和和e6e6之間無之間無 路徑路徑 P1P1P2P2P3P3e e1 1e e2 2e e4 4e e3 3e e7 7e e5

15、 5e e8 8e e6 6time144.2 因果關(guān)系因果關(guān)系n HDAG 有時將有時將Happens-before關(guān)系描述為一個有向無環(huán)圖關(guān)系描述為一個有向無環(huán)圖v頂點集頂點集V VH H是事件集是事件集E E：eVeVH H 當且僅當當且僅當 eeE E v邊集邊集E EH H：若：若(e(e1 1，e e2 2)E)EH H 當且僅當當且僅當e e1 1 Pe e2 2或或e e1 1 me e2 2 P1P1P2P2P3P3e e1 1e e2 2e e4 4e e3 3e e7 7e e5 5e e8 8e e6 6timee e1 1e e2 2e e4 4e e3 3e e7

16、7e e5 5e e8 8e e6 6154.2.1 Lamport時間戳時間戳n 系統(tǒng)有序性的重要性系統(tǒng)有序性的重要性 若分布式系統(tǒng)中存在全局時鐘，則系統(tǒng)中的事件均可若分布式系統(tǒng)中存在全局時鐘，則系統(tǒng)中的事件均可安排為全序。例如，可以更公平地分配系統(tǒng)資源。安排為全序。例如，可以更公平地分配系統(tǒng)資源。n 全序?qū)κ录挠绊懞陀扇驅(qū)κ录挠绊懞陀蒆關(guān)系確定的偏序?qū)κ录挠瓣P(guān)系確定的偏序?qū)κ录挠绊懯且恢碌捻懯且恢碌膎 如何通過如何通過H關(guān)系確定的偏序關(guān)系來建立一個關(guān)系確定的偏序關(guān)系來建立一個“一致一致”的全序關(guān)系？的全序關(guān)系？v在在 H的的DAGDAG上拓撲排序上拓撲排序 vOn the fly

17、：Lamport提出了動態(tài)即時地建立全序提出了動態(tài)即時地建立全序算法算法 164.2.1 Lamport時間戳時間戳n Lamport算法的算法的思想思想 每個每個事件事件e有一個附加的時戳：有一個附加的時戳：e.TS 每個每個節(jié)點節(jié)點有一個局部時戳：有一個局部時戳：my_TS 每個每個msg有一個附加時間戳：有一個附加時間戳：m.TS 節(jié)點節(jié)點執(zhí)行執(zhí)行一個事件時，將自己的時戳賦給該一個事件時，將自己的時戳賦給該事件事件； 節(jié)點發(fā)送節(jié)點發(fā)送msg時，將自己的時戳賦給所有時，將自己的時戳賦給所有發(fā)送發(fā)送的的msg。 174.2.1 Lamport時間戳時間戳n Lamport算法的算法的實現(xiàn)實現(xiàn)

18、 Initially：my_TS=0; On event e： if ( e是接收消息是接收消息m ) then my_TS = max ( m.TS, my_TS ); /取取msg時戳和節(jié)點時戳的較大者作為新時戳時戳和節(jié)點時戳的較大者作為新時戳 my_TS+; e.TSmy_TS; /給事件給事件e打時戳打時戳 if ( e是發(fā)送消息是發(fā)送消息m ) then m.TSmy_TS; /給消息給消息m打時戳打時戳184.2.1 Lamport時間戳時間戳nLamport算法賦值的時戳是因果相關(guān)的算法賦值的時戳是因果相關(guān)的 若若e e1 1 He e2 2，則，則 e e1 1.TS e.TS

19、 e2 2.TS.TS 若若e e1 1 Pe e2 2或或e e1 1 me e2 2，則的，則的e e2 2時戳大于時戳大于e e1 1的時戳的時戳 在因果事件鏈上，每一事件的時戳大于其前驅(qū)事在因果事件鏈上，每一事件的時戳大于其前驅(qū)事件的時戳件的時戳n問題：系統(tǒng)中所有事件已為全序？問題：系統(tǒng)中所有事件已為全序？ 不同的事件可能有相同的時戳（并發(fā)事件）不同的事件可能有相同的時戳（并發(fā)事件）nLamport算法改進算法改進 因為并發(fā)事件的時戳可以任意指定先后因為并發(fā)事件的時戳可以任意指定先后 故可用節(jié)點地址作為時戳的低位故可用節(jié)點地址作為時戳的低位194.2.1 Lamport時間戳時間戳n

20、改進的改進的Lamport時戳時戳 事件標號：時戳事件標號：時戳.id.id 事件事件e8e8為為4.3:4.3: my_TS=max(m.TS,my_TS my_TS=max(m.TS,my_TS) ) =max(3,1)=3 =max(3,1)=3 按字典序得全序：按字典序得全序： 1.1, 1.2, 1.3, 2.1, 2.2, 3.1, 3.2, 4.31.1, 1.2, 1.3, 2.1, 2.2, 3.1, 3.2, 4.3n 算法特點：分布、容錯、系統(tǒng)開銷小算法特點：分布、容錯、系統(tǒng)開銷小n Lamport算法的迷人之處在于：任何進程在發(fā)送消息前，先將自己的本地算法的迷人之處在于

21、：任何進程在發(fā)送消息前，先將自己的本地計數(shù)器累加計數(shù)器累加1；接收進程總是計算自己的本地計數(shù)器和接受到計數(shù)器中較大；接收進程總是計算自己的本地計數(shù)器和接受到計數(shù)器中較大值加上值加上1的結(jié)果的結(jié)果timeP1P1P2P2P3P3e e1 1e e2 2e e4 4e e3 3e e7 7e e5 5e e8 8e e6 61 1. .2 22 2. .2 23 3. .2 23 3. .1 12 2. .1 11 1. .1 14 4. .3 31 1. .3 3204.2.2 向量時間戳向量時間戳nLamport時戳缺點時戳缺點 若若e e1 1 He e2 2，則，則 e e1 1.TS e

22、.TS e2 2.TS.TS；反之不然。；反之不然。 例如：例如：1.32.11.32.1，但是，但是e e6 6ee4 4不成立不成立 原因：并發(fā)事件之間的次序是任意的原因：并發(fā)事件之間的次序是任意的 不能通過事件的不能通過事件的時戳判定時戳判定兩事件之間是否是兩事件之間是否是因果相關(guān)因果相關(guān)n判定事件間因果關(guān)系的重要性判定事件間因果關(guān)系的重要性 例子：違反因果關(guān)系檢測例子：違反因果關(guān)系檢測 在一個分布式對象系統(tǒng)中，為了負載平衡，對象是可在一個分布式對象系統(tǒng)中，為了負載平衡，對象是可移動的，對象在處理器之間遷移是為了獲得所需的調(diào)移動的，對象在處理器之間遷移是為了獲得所需的調(diào)用的進程或資源。如

23、下圖：用的進程或資源。如下圖： 214.2.2 向量時戳向量時戳1)P1持有對象持有對象O，決定遷移到，決定遷移到P2 為獲取資源，為獲取資源，P1P1將將O裝配在消息裝配在消息 M1中發(fā)送給中發(fā)送給P22)P1收到收到P3訪問訪問O的請求的請求 P1將將O的新地址的新地址P2放在消息放在消息M2 中通知中通知P33)P3在在M3中請求訪問中請求訪問P2的的O 當當M3 3達到達到P2P2時，時，O不可用，故不可用，故 回答一個出錯消息?；卮鹨粋€出錯消息。n 問題：當問題：當debug該系統(tǒng)時，會發(fā)該系統(tǒng)時，會發(fā) 現(xiàn)現(xiàn)O已在已在P2上，故不知錯在哪？上，故不知錯在哪？P1P1P2P2P3P3M

24、1On P2On P2Where Where is is O? ?遷移遷移O到到P2P2I dont knowM2Where Where is is O? ?M3Error!Error!224.2.2 向量時間戳向量時間戳n 錯誤原因：違反因果序錯誤原因：違反因果序 P3請求請求O是發(fā)生在從是發(fā)生在從P1遷移到遷移到P2之后，但該請求被處理是在遷之后，但該請求被處理是在遷移達到移達到P2之前。形式地，之前。形式地， 設(shè)：設(shè)：s(m)是發(fā)送是發(fā)送m的事件的事件 r(m)是接收是接收m的事件的事件 若若s(m1)s(m1)H s(m2)s(m2)，則稱消息，則稱消息m1m1因果關(guān)系上先于因果關(guān)系上

25、先于m2m2，記做，記做m1m1C m2m2 若若m1 m1 C m2m2，但，但 r(m2) r(m2) P r(m1)r(m1)，則，則違反違反“因果關(guān)系因果關(guān)系”： 即，若即，若m1m1先于先于m2m2發(fā)送，但在發(fā)送，但在同一節(jié)點同一節(jié)點P P上上m2m2在在m1m1之前被接收之前被接收 例如，在上例中有：例如，在上例中有： M1CM3，但，但 r(M3) P2 r(M1)234.2.2 向量時間戳向量時間戳n 違反因果序檢測違反因果序檢測v定義：定義：若時戳若時戳VT具有比較函數(shù)具有比較函數(shù) V滿足：滿足： e1e1H e2 e2 iff e1.VTe1.VTV e2.VTe2.VT

26、則我們能夠檢測出是否違反因果關(guān)系則我們能夠檢測出是否違反因果關(guān)系vVTVT性質(zhì)性質(zhì) 1 1）因）因 H 是偏序，故是偏序，故 V 也是偏序；也是偏序； 2 2）因為必須知道在因果關(guān)系上每一節(jié)點中哪些事件是在事）因為必須知道在因果關(guān)系上每一節(jié)點中哪些事件是在事 件件e e之前，故之前，故e.VTe.VT中必須包含系統(tǒng)中每一個其它節(jié)點的中必須包含系統(tǒng)中每一個其它節(jié)點的 狀態(tài)。狀態(tài)。 這兩個性質(zhì)導致了這兩個性質(zhì)導致了向量時戳向量時戳VTVT的引入的引入244.2.2 向量時戳向量時戳n 向量時戳向量時戳VT VT是一個整數(shù)數(shù)組：是一個整數(shù)數(shù)組： e.VTi=k表示在節(jié)點表示在節(jié)點i（或（或 Pi）上

27、，因果關(guān)系上）上，因果關(guān)系上e之前有之前有k 個事件（可能包括個事件（可能包括e自己）。自己）。 e.VT=(3,6,4,2)表示因果序：表示因果序： 在在P1上，有上，有3個事件須在個事件須在e之前之前 在在P2上，有上，有6個事件須在個事件須在e之前之前 在在P3上，有上，有4個事件須在個事件須在e之前之前 在在P4上，有上，有2個事件須在個事件須在e之前之前P1P1P2P2P3P31 1P4P43 32 25 54 43 31 12 21 15 54 41 16 64 42 23 31 13 32 2e e254.2.2 向量時間戳向量時間戳n 向量時戳的意義向量時戳的意義在因果關(guān)系上，

28、在因果關(guān)系上，e1.VT e1.VT V e2.VTe2.VT表示表示e2e2發(fā)生在發(fā)生在 e1e1及及e1e1前所有的前所有的事件之后。事件之后。更精確的說，向量時鐘的次序為：更精確的說，向量時鐘的次序為： e1.VTe1.VTV e2.VTe2.VT iff e1.VTie1.VTi e2.VTie2.VTi,i=1,2,i=1,2,M,M e1.VT e1.VTV e2.VTe2.VT iff e1.VTe1.VT VTe2.VTe2.VT且且e1.VTe2.VTe1.VTe2.VT n 向量時戳算法向量時戳算法 my_VT：每個節(jié)點有局部的向量時戳每個節(jié)點有局部的向量時戳 e.VT：每

29、個事件有向量時戳每個事件有向量時戳 m.VT：每個每個msg有向量時戳有向量時戳 節(jié)點節(jié)點執(zhí)行執(zhí)行一個事件時，將自己的時戳賦給該一個事件時，將自己的時戳賦給該事件事件； 節(jié)點節(jié)點發(fā)送發(fā)送msg時，將自己的時戳賦給所有時，將自己的時戳賦給所有發(fā)送發(fā)送的的msg。注意注意V, VT以及以及V之間的區(qū)別之間的區(qū)別：V代表因果序，代表因果序，而而VT代表時戳比較代表時戳比較264.2.2 向量時間戳向量時間戳n 算法算法實現(xiàn)實現(xiàn) Initially：my_VT=0,0; On event e： if ( e是消息是消息m的接收者的接收者 ) then for i=1 to M do /向量時戳的每個分

30、量只增不減向量時戳的每個分量只增不減 my_VT i = max( m.VTi, my_VTi ); my_VT self +; /設(shè)變量設(shè)變量self是本節(jié)點的名字是本節(jié)點的名字 e.VTmy_VT; /給事件給事件e打時戳打時戳 if ( e是消息是消息m的發(fā)送者的發(fā)送者 ) then m.VTmy_VT; /給消息給消息m打時戳打時戳274.2.2 向量時間戳向量時間戳n 算法性質(zhì)算法性質(zhì) 1）若）若e eH e e，則，則e.VTe.VTVT e e.VT.VT 算法確保對于每個事件滿足：算法確保對于每個事件滿足： 若若e eP e e或或e em e e ，則，則e.VTe.VTVT

31、 e e.VT.VT 2）若）若e eH e e，則，則e.VTe.VTVT e e.VT.VT pf：若若e e和和e e 因果相關(guān)，則有因果相關(guān)，則有e eH e e，即，即e e.VT.VTe2.VT1 e1.VT2e2.VT2 e1e1到到e2e2及及e2e2到到e1e1均無路徑均無路徑 2 2）e3e3在因果序上先于在因果序上先于e1e1 即：即：e3.VTe3.VTV e1.VTe1.VT e1 e1的前驅(qū)事件見方框的前驅(qū)事件見方框P1P1P2P2P3P310001000P4P43300330023002300541354134400440013001300120012000100

32、010035003500140014000010001036423642014201420120012001320132001100110013001300120012e2e2e3e3e1e1294.2.2 向量時戳向量時戳n 因果序檢測因果序檢測 1)1)消息時戳間比較消息時戳間比較 在在P2P2上，先到達的上，先到達的M3的時戳為的時戳為 （3,0,3），后到達的），后到達的M1的時戳的時戳 為（為（1,0,0）。但是：）。但是： (1,0,0)V (3,0,3) M1在因果序上先于在因果序上先于M3 故故M1后于后于M3到達違反因果序到達違反因果序 2)2)消息時戳和局部時戳比較消息時戳

33、和局部時戳比較 當當時戳為時戳為(1,0,0) 的的M1到達到達P2 時，時，P2的時戳是的時戳是(3,2,3)。但：。但： (1,0,0)V (3,2,3) M1在因果序上應先于在因果序上應先于(3,2,3)對應的事件對應的事件P1P1P2P2P3P3M1On P2On P2Where Where is is O? ?遷移遷移O到到P2P2I dont knowM2Where Where is is O? ?M3Error!Error!100100201201301301001001302302303303313313323323333333324324304.2.3 因果通信因果通信n 如

34、何保證通信不違反因果如何保證通信不違反因果關(guān)系？關(guān)系？ 處理器不能選擇處理器不能選擇msgmsg達到達到的次序，但能的次序，但能抑制抑制過早達過早達到的到的msgmsg來修正傳遞（指來修正傳遞（指提交給應用）次序。提交給應用）次序。 n FIFO通信（如通信（如TCP） 由由msg傳遞協(xié)議棧里的一傳遞協(xié)議棧里的一層負責確保層負責確保FIFO通信通信ApplicationFIFO orderingDeliver in FIFO orderMsg passinga s s i g n timestamps314.2.3 因果通信因果通信nFIFO通信通信 源處理器給每個發(fā)送的源處理器給每個發(fā)送的m

35、sg順序編號，目的處理器知道自順序編號，目的處理器知道自己所收到的己所收到的msg應該有何順序的編號，若目的處理器收到應該有何順序的編號，若目的處理器收到一個編號為一個編號為x的的msg但未收到較小編號的但未收到較小編號的msg時，則延遲傳時，則延遲傳遞直至能夠順序傳遞為止。遞直至能夠順序傳遞為止。n因果通信因果通信 因果通信與因果通信與FIFO通信類似通信類似 源：附上時戳源：附上時戳 目的地：延遲錯序目的地：延遲錯序msgMsg 達到次序達到次序X2deliverx2X5bufferx5X1deliverx1X4bufferx4X3deliverx3x4x5324.2.3 因果通信因果通信n 因果通信實現(xiàn)思想因果通信