時(shí)間和全局狀態(tài)

第3章時(shí)間和全局狀態(tài)第3章時(shí)間和全局狀態(tài)簡(jiǎn)介

時(shí)鐘、事件和進(jìn)程狀態(tài)同步物理時(shí)鐘邏輯時(shí)間和邏輯時(shí)鐘全局狀態(tài)分布式調(diào)試小結(jié)簡(jiǎn)介如何計(jì)時(shí)？如何同步時(shí)鐘？沒(méi)有物理時(shí)鐘能否確定事件的順序？簡(jiǎn)介時(shí)間的重要性需要精確度量——審計(jì)電子商務(wù)某些算法依賴于時(shí)鐘同步——數(shù)據(jù)一致性維護(hù)、make計(jì)算全局狀態(tài)——事件排序時(shí)間的復(fù)雜性節(jié)點(diǎn)具有獨(dú)立的物理時(shí)鐘精確同步物理時(shí)鐘非常困難全局狀態(tài)的捕獲依賴于邏輯時(shí)鐘邏輯時(shí)鐘與物理時(shí)鐘無(wú)必然聯(lián)系時(shí)鐘、事件和進(jìn)程狀態(tài)時(shí)間分類(lèi)天文學(xué)時(shí)間

-太陽(yáng)日：兩次連續(xù)的太陽(yáng)中天之間的時(shí)間間隔

-太陽(yáng)秒：1/86400個(gè)太陽(yáng)日國(guó)際原子時(shí)間(TAI)-基于銫原子跳躍周期

-秒：9192631770次跳躍周期通用協(xié)調(diào)時(shí)間(UTC)-基于原子時(shí)間

-采用潤(rùn)秒，與天文時(shí)間保持一致第3章時(shí)間和全局狀態(tài)簡(jiǎn)介

時(shí)鐘、事件和進(jìn)程狀態(tài)同步物理時(shí)鐘邏輯時(shí)間和邏輯時(shí)鐘全局狀態(tài)分布式調(diào)試小結(jié)時(shí)鐘、事件和進(jìn)程狀態(tài)假設(shè)每個(gè)進(jìn)程在單處理器上執(zhí)行處理器之間不共享內(nèi)存進(jìn)程之間通過(guò)消息進(jìn)行通信進(jìn)程狀態(tài)所有變量的值相關(guān)的本地操作系統(tǒng)環(huán)境中的對(duì)象的值事件定義：一個(gè)通信動(dòng)作或進(jìn)程狀態(tài)轉(zhuǎn)換動(dòng)作進(jìn)程歷史：時(shí)鐘、事件和進(jìn)程狀態(tài)計(jì)算機(jī)時(shí)鐘晶體具有固定震蕩頻率硬件時(shí)鐘：軟件時(shí)鐘：時(shí)鐘漂移頻率不同時(shí)鐘頻率隨溫度變化而有所差別時(shí)鐘偏移不可避免Infact,theeffectofclockskewisthemainreasonwhyclockoffsetskeepdriftingaway.Novelclockphaseoffset……IEEETransactionsonCommnunications,Vol55,No.4,2007.4第3章時(shí)間和全局狀態(tài)簡(jiǎn)介

時(shí)鐘、事件和進(jìn)程狀態(tài)同步物理時(shí)鐘邏輯時(shí)間和邏輯時(shí)鐘全局狀態(tài)分布式調(diào)試小結(jié)同步物理時(shí)鐘外部同步采用權(quán)威的外部時(shí)間源時(shí)鐘Ci在范圍D內(nèi)是準(zhǔn)確的內(nèi)部同步無(wú)外部權(quán)威時(shí)間源,系統(tǒng)內(nèi)時(shí)鐘同步時(shí)鐘Ci在范圍D內(nèi)是準(zhǔn)確的關(guān)系

若P在范圍D內(nèi)外部同步,則P在范圍2D內(nèi)內(nèi)部同步同步物理時(shí)時(shí)鐘Cristian方法(適用于只有有一臺(tái)機(jī)器器有WWV接收器)應(yīng)用條件-存在時(shí)間服服務(wù)器，可可與外部時(shí)時(shí)間源同步步-消息往返時(shí)時(shí)間與系統(tǒng)統(tǒng)所要求的的精度相比比足夠短協(xié)議-進(jìn)程p根據(jù)消息mr，mt計(jì)算消息往往返時(shí)間Tround-根據(jù)服務(wù)器器在mt中放置的時(shí)時(shí)間t設(shè)置時(shí)鐘為為：t+Tround/2mtp時(shí)間服務(wù)器Smr同步物理時(shí)時(shí)鐘Berkeley算法（沒(méi)有有WWV接收器）主機(jī)周期輪詢從屬機(jī)時(shí)間間主機(jī)通過(guò)消消息往返時(shí)時(shí)間估算從從屬機(jī)的時(shí)時(shí)間與Cristian方法類(lèi)似主機(jī)計(jì)算容錯(cuò)平均值值主機(jī)發(fā)送每每個(gè)從屬機(jī)機(jī)的調(diào)整量同步物理時(shí)時(shí)鐘網(wǎng)絡(luò)時(shí)間協(xié)協(xié)議(NTP)設(shè)計(jì)目標(biāo)-可外部同步步使得跨Internet的用戶能精精確地與UTC同步-高可靠性可處理連接接丟失，采采用冗余服服務(wù)器、路路徑等-擴(kuò)展性好大量用戶可可經(jīng)常同步步，以抵消消漂移率的的影響-安全性強(qiáng)防止惡意或或偶然的干干擾同步物理時(shí)時(shí)鐘協(xié)議結(jié)構(gòu)-層次結(jié)構(gòu)-主服務(wù)器直直接與外部部UTC同步-同步子網(wǎng)可可重新配置置123233

同步子網(wǎng)結(jié)構(gòu)示例第3章時(shí)間和和全局狀態(tài)態(tài)簡(jiǎn)介時(shí)鐘、事件件和進(jìn)程狀狀態(tài)物理時(shí)鐘同同步邏輯時(shí)間和和邏輯時(shí)鐘鐘全局狀態(tài)分布式調(diào)試試小結(jié)邏輯時(shí)間和和邏輯時(shí)鐘鐘邏輯時(shí)間的的引入分布式系統(tǒng)統(tǒng)中的物理理時(shí)鐘無(wú)法法完美同步步-消息傳輸延延時(shí)的不確確定性事件排序是是眾多分布布式算法的的基石-互斥算法-死鎖檢測(cè)算算法缺乏全局時(shí)時(shí)鐘-后發(fā)生的事事件有可能能賦予較早早的時(shí)間標(biāo)標(biāo)記邏輯時(shí)間和和邏輯時(shí)鐘鐘邏輯時(shí)鐘眾多應(yīng)用只只要求所有有節(jié)點(diǎn)具有有相同時(shí)間，該時(shí)間不一定與實(shí)實(shí)際時(shí)間相相同Lamport(1978)指出：不進(jìn)進(jìn)行交互的的兩個(gè)進(jìn)程程之間不需需要時(shí)鐘同同步對(duì)于不需要要交互的兩兩個(gè)進(jìn)程而而言，即使使沒(méi)有時(shí)鐘鐘同步，也也無(wú)法察覺(jué)覺(jué)，更不會(huì)會(huì)產(chǎn)生問(wèn)題題。所有的進(jìn)程程需要在時(shí)時(shí)間的發(fā)生順序上達(dá)成一致如make程序邏輯時(shí)間和和邏輯時(shí)鐘鐘事件排序“系統(tǒng)i中的事件a發(fā)生在系統(tǒng)統(tǒng)j中的事件b之前”是不不準(zhǔn)確的-事件發(fā)生和和觀察之間間存在時(shí)延延-不同系統(tǒng)中中的時(shí)鐘存存在偏差時(shí)間戳(Lamport1978)-用于分布式式系統(tǒng)中的的事件排序序-與物理時(shí)鐘鐘無(wú)關(guān)-實(shí)用高效，，應(yīng)用廣泛泛邏輯時(shí)間和和邏輯時(shí)鐘鐘兩個(gè)基本事事實(shí)-同一進(jìn)程中中的兩個(gè)事事件存在關(guān)關(guān)系“i”-任一消息的的發(fā)送事件件發(fā)生在該該消息的接接收事件之之前“發(fā)生在先先(happens-before)””關(guān)系定義-若存在進(jìn)程程pi滿足eie’，則ee’-對(duì)于任一消消息m，存在send(m)recv(m)-若事件滿足足ee’和e’e’’，則ee’’并發(fā)關(guān)系定定義XY與YX均不成立，，則稱事件件X、Y是并發(fā)的，，表示為X||Y邏輯時(shí)間和和邏輯時(shí)鐘鐘事件排序示示例-bc，cd和df成立-bf與ef均成立-事件b和e無(wú)法比較，，即b||ep1p2p3abcdefm1m2物理時(shí)間邏輯時(shí)間和和邏輯時(shí)鐘鐘Lamport時(shí)鐘機(jī)制-進(jìn)程維護(hù)一一個(gè)單調(diào)遞遞增的軟件件計(jì)數(shù)器，，充當(dāng)邏輯輯時(shí)鐘-用邏輯時(shí)鐘鐘為事件添添加時(shí)間戳戳-按事件的時(shí)時(shí)間戳大小小為時(shí)間排排序邏輯時(shí)鐘修修改規(guī)則-進(jìn)程pi發(fā)出事件前前，邏輯時(shí)時(shí)鐘Li:=Li+1-進(jìn)程pi發(fā)送消息m時(shí)，在m中添加時(shí)間間戳t=Li-進(jìn)程pj在接收(m,t)時(shí)，更新Li:=max(Lj,t)+1，給s事件件recv(m)添加時(shí)間戳戳后發(fā)送給給應(yīng)用程序序abcdefm1m2213451p1p2p3物理時(shí)間邏輯時(shí)間和和邏輯時(shí)鐘鐘Lamport時(shí)鐘示例(一)abL(a)<L(b)L(e)<L(b)be邏輯時(shí)間和和邏輯時(shí)鐘鐘(a)三個(gè)不同速速率的時(shí)鐘鐘(b)Lamport算法校正時(shí)時(shí)鐘Lamport時(shí)鐘示例(二)邏輯時(shí)間和和邏輯時(shí)鐘鐘Lamport時(shí)鐘練習(xí)假設(shè)系統(tǒng)中中只存在消消息發(fā)送和和接收事件件，如下圖圖所示，請(qǐng)請(qǐng)給出事件件a-g的邏輯時(shí)鐘鐘。邏輯時(shí)鐘0邏輯時(shí)間和和邏輯時(shí)鐘鐘Lamport時(shí)鐘練習(xí)答案邏輯時(shí)鐘：：0144328657579邏輯時(shí)間間和邏輯輯時(shí)鐘不同進(jìn)程產(chǎn)生生的消息息可能具具有相同數(shù)值值的Lamport時(shí)間戳物理時(shí)間邏輯時(shí)間間和邏輯輯時(shí)鐘基于Lamport時(shí)間戳的的事件排排序---總結(jié)算法不依依賴于事事件發(fā)生生的真實(shí)實(shí)時(shí)間與真實(shí)物物理時(shí)間間中事件件的發(fā)生生順序可可能不一一致基于Lamport時(shí)間戳的的排序中中，在時(shí)時(shí)刻(2,1)發(fā)生的事事件發(fā)生生比在時(shí)時(shí)刻（2，2）發(fā)生的事事件要早早，然而而在真實(shí)實(shí)物理時(shí)時(shí)間中可可能恰好好相反。。邏輯時(shí)間間和邏輯輯時(shí)鐘Lamport時(shí)鐘不具具備性質(zhì)質(zhì)：若L(A)<L(B)則AB沒(méi)有捕獲獲事件的的因果關(guān)關(guān)系節(jié)點(diǎn)B發(fā)布一篇篇文章并并傳送給給節(jié)點(diǎn)A和C。節(jié)點(diǎn)A就此發(fā)表表評(píng)論并并傳送給給節(jié)點(diǎn)B和C。araarr我們無(wú)法法準(zhǔn)確確確定r的先后關(guān)關(guān)系：C(a)<C(r)ara是節(jié)點(diǎn)A發(fā)布的文文章r是節(jié)點(diǎn)B對(duì)文章a的評(píng)論全序邏輯輯時(shí)鐘引入進(jìn)程程標(biāo)示符符創(chuàng)建事事件的全全序關(guān)系系若e、e’分別為進(jìn)進(jìn)程pi、pj中發(fā)生的的事件，，則其全全局邏輯輯時(shí)間戳戳分別為為(Ti,i)、(Tj,j)。ee’Ti<Tj||Ti=Tj&&i<j系統(tǒng)中各各個(gè)事件件Lamport時(shí)間戳均均不相同同向量時(shí)鐘鐘克服Lamport時(shí)鐘的缺缺點(diǎn)：若L(e)<L(e’)不能推出出則ee’。每個(gè)進(jìn)程程維護(hù)它它自己的的向量時(shí)時(shí)鐘ViVC1:初始情況況下，Vi[j]=0,i,j=1,2,...N.VC2:在pi給事件加加時(shí)間戳戳之前，，設(shè)置Vi[i]=Vi[i]+1。VC3:pi在它發(fā)送送的每個(gè)個(gè)消息中中包括t＝Vi。VC4：當(dāng)pi接收到消消息中的的時(shí)間戳戳t時(shí)，設(shè)置置Vi[j]=max(Vi[j],t[j]),j=1,2,...,N。向量時(shí)鐘鐘Host1Host2Host3Host40,0,0,0VectorlogicalclockMessage(vectortimestamp)PhysicalTime0,0,0,00,0,0,00,0,0,0(1,0,0,0)1,0,0,01,1,0,02,0,0,02,0,1,0(2,0,0,0)2,0,2,02,0,2,1(2,0,2,0)1,2,0,02,2,3,0(1,2,0,0)4,0,2,24,2,4,2(4,0,2,2)2,0,2,23,0,2,2(2,0,2,2)2,0,2,34,2,5,3(2,0,2,3)n,m,p,q向量時(shí)鐘鐘第3章時(shí)間間和全局局狀態(tài)簡(jiǎn)介時(shí)鐘、事事件和進(jìn)進(jìn)程狀態(tài)態(tài)同步物理理時(shí)鐘邏輯時(shí)間間和邏輯輯時(shí)鐘全局狀態(tài)態(tài)分布式調(diào)調(diào)試小結(jié)全局狀態(tài)態(tài)觀察全局局狀態(tài)的的必要性性分布式無(wú)無(wú)用單元元的收集集-基于對(duì)象象的引用用計(jì)數(shù)-必須考慮慮信道和和進(jìn)程的的狀態(tài)分布式死死鎖檢測(cè)測(cè)觀察系統(tǒng)統(tǒng)中的““等待””關(guān)系圖圖中是否否存在循循環(huán)p1消息無(wú)用對(duì)象對(duì)象引用p2等待等待p1p2分布式終終止檢測(cè)測(cè)與進(jìn)程的的狀態(tài)有有關(guān)——“主動(dòng)”或“被動(dòng)”分布式調(diào)調(diào)試需要收集集同一時(shí)時(shí)刻系統(tǒng)統(tǒng)中分布布式變量量的數(shù)值值全局狀態(tài)態(tài)激活被動(dòng)的p1p2被動(dòng)的全局狀態(tài)態(tài)全局狀態(tài)態(tài)和一致致割集觀察進(jìn)程程集的狀狀態(tài)——全局狀態(tài)態(tài)非常困困難根源：缺缺乏全局局時(shí)間進(jìn)程的歷歷史hi=<ei0,ei1,ei2…>進(jìn)程歷史史的有限限前綴hik=<ei0,ei1,…,eik>全局歷史史——單個(gè)進(jìn)程程歷史的的并集H=h1h2…h(huán)N全局狀態(tài)進(jìn)程狀態(tài)sik:進(jìn)程pi在第k個(gè)事件發(fā)生之之前的狀態(tài)全局狀態(tài)——單個(gè)進(jìn)程狀態(tài)態(tài)的集合S=(s1,s2,…sN)割集——系統(tǒng)全局歷史史的子集C=<h1c1,h2c2…h(huán)3c3>割集的一致性性割集C是一致的:對(duì)于所有事件件eC,fefC全局狀態(tài)割集示例m1m2p1p2物理時(shí)間e10一致的割集不一致的割集e11e12e13e20e21e22全局狀態(tài)一致的全局狀狀態(tài)——對(duì)應(yīng)于一致割割集的狀態(tài)S0S1S2…走向(run)-全局歷史中所所有事件的全全序-與每個(gè)本地歷歷史順序一致致-不是所有的走走向都經(jīng)歷一一致的全局狀狀態(tài)線性化走向-所有的線性化化走向只經(jīng)歷歷一致的全局局狀態(tài)-若存在一個(gè)經(jīng)經(jīng)過(guò)S和S’的線性化走向向，則狀態(tài)S’是從S可達(dá)全局狀態(tài)Chandy和Lamport的“快照”算算法目的捕獲一致的全全局狀態(tài)假設(shè)-進(jìn)程和通道均均不會(huì)出現(xiàn)故故障-單向通道，提提供FIFO順序的消息傳傳遞-進(jìn)程之間存在在全連通關(guān)系系-任一進(jìn)程可在在任一時(shí)間開(kāi)開(kāi)始全局拍照照-拍照時(shí)，進(jìn)程程可繼續(xù)執(zhí)行行，并發(fā)送和和接收消息全局狀態(tài)算法基本思想想-接入通道+外出通道-進(jìn)程狀態(tài)+通道狀態(tài)-標(biāo)記消息標(biāo)記接收規(guī)則則：強(qiáng)制進(jìn)程在在記錄下自己己的狀態(tài)之后后但在它們發(fā)發(fā)送其他消息息前發(fā)送一個(gè)個(gè)標(biāo)記。標(biāo)記發(fā)送規(guī)則則：強(qiáng)制沒(méi)有記記錄狀態(tài)的進(jìn)進(jìn)程去記錄狀狀態(tài)全局狀態(tài)算法偽碼(一)進(jìn)程pi的標(biāo)記接收規(guī)規(guī)則pi接收通道c上的標(biāo)記消息息：if(pi還沒(méi)有記錄它它的狀態(tài))pi記錄它的進(jìn)程程狀態(tài)；將c的狀態(tài)記成空空集；開(kāi)始記錄從其其他接入通道道上到達(dá)的消消息elsepi把c的狀態(tài)記錄到到從保留它的的狀態(tài)以來(lái)它它在c上接收到的消消息集合中endif全局狀態(tài)算法偽碼(二)進(jìn)程pi的標(biāo)記發(fā)送規(guī)規(guī)則在pi記錄了它的狀狀態(tài)之后，對(duì)對(duì)每個(gè)外出通通道c:(在pi從c上發(fā)送任何其其他消息前)pi在c上發(fā)送一個(gè)消消息標(biāo)記全局狀態(tài)算法示例-兩個(gè)進(jìn)程p1、p2進(jìn)行交易，每每件10$-初始狀態(tài)進(jìn)程p2已經(jīng)收到5件商品的定單單，它將馬上上分發(fā)給p1p1p2c2c1帳戶窗口部件$1000(none)帳戶窗口部件$502000全局狀態(tài)最后狀態(tài)：P1:<$1000,0>;p2:<$50,1995>;c1:<(fivewidgets)>;c2:<>p1(空)<$1000,0>1.全局狀態(tài)S0p1p1p1c2c1(空)2.全局狀態(tài)S1<$900,0><$900,0><$900,5><$50,1995><$50,1995><$50,2000><$50,2000>3.全局狀態(tài)S24.全局狀態(tài)S3p2p2p2p2c2c2c2c1c1c1(定單10，$100)，M(空)(空)(定單10，$100)，M(五個(gè)窗口部件)M=標(biāo)記信息)(定單10，$100)全局局狀狀態(tài)態(tài)算法法終終止止-假設(shè)設(shè)：：一一個(gè)個(gè)進(jìn)進(jìn)程程已已經(jīng)經(jīng)收收到到了了一一個(gè)個(gè)標(biāo)標(biāo)記記信信息息，，在在有有限限的的時(shí)時(shí)間間內(nèi)內(nèi)記記錄錄了了它它的的狀狀態(tài)態(tài)，，并并在在有有限限的的時(shí)時(shí)間間里里通通過(guò)過(guò)每每個(gè)個(gè)外外出出通通道道發(fā)發(fā)送送了了標(biāo)標(biāo)記記信信息息．．-若存存在在一一條條從從進(jìn)進(jìn)程程pi到進(jìn)進(jìn)程程pj的信信道道和和進(jìn)進(jìn)程程的的路路徑徑，，那那么么pi記錄錄它它的的狀狀態(tài)態(tài)之之后后的的有有限限時(shí)時(shí)間間內(nèi)內(nèi)pj將記記錄錄它它的的狀狀態(tài)態(tài)．．-進(jìn)程程和和通通道道圖圖是是強(qiáng)強(qiáng)連連接接的的，，因因此此在在一一些些進(jìn)進(jìn)程程記記錄錄它它的的狀狀態(tài)態(tài)之之后后的的有有限限時(shí)時(shí)間間內(nèi)內(nèi)，，所所有有進(jìn)進(jìn)程程將將記記錄錄它它們們的的狀狀態(tài)態(tài)和和節(jié)節(jié)入入通通道道的的狀狀態(tài)態(tài)。。全局局狀狀態(tài)態(tài)算法法一一致致性性ei、ej分別別為為進(jìn)進(jìn)程程pi、pj中的的事事件件，，且且eiej則我我們們有有:若ejCeiC，其其中中C為一一個(gè)個(gè)割割集集。。即即如如果果ej在pj記錄錄它它的的狀狀態(tài)態(tài)之之前前發(fā)發(fā)生生，，那那么么ei必須須在在pi記錄錄它它的的狀狀態(tài)態(tài)之之前前發(fā)發(fā)生生.證明明思思路路如如下下：：-i=j時(shí)，，顯顯然然成成立立-i≠≠j時(shí)，，反反證證法法第3章時(shí)時(shí)間間和和全全局局狀狀態(tài)態(tài)簡(jiǎn)介介時(shí)鐘鐘、、事事件件和和進(jìn)進(jìn)程程狀狀態(tài)態(tài)物理理時(shí)時(shí)鐘鐘同同步步邏輯輯時(shí)時(shí)間間和和邏邏輯輯時(shí)時(shí)鐘鐘全局局狀狀態(tài)態(tài)分布布式式調(diào)調(diào)試試小結(jié)結(jié)分布布式式調(diào)調(diào)試試目的的對(duì)系系統(tǒng)統(tǒng)實(shí)實(shí)際際執(zhí)執(zhí)行行中中的的暫暫態(tài)態(tài)作作出出判判斷斷例子子安全全條條件件檢檢查查xi為進(jìn)進(jìn)程程pi的變變量量(i=1,2,…)，安安全全條條件件為為|xi-xj|≤≤控制制系系統(tǒng)統(tǒng)所有有閥閥門(mén)門(mén)在在某某些些時(shí)時(shí)間間是是否否全全部部處處于于開(kāi)開(kāi)啟啟狀狀態(tài)態(tài)分布布式式調(diào)調(diào)試試方法法監(jiān)控控器器進(jìn)進(jìn)程程收集集進(jìn)進(jìn)程程狀狀態(tài)態(tài)信信息息全局局狀狀態(tài)態(tài)謂謂詞詞的的判判斷斷-可能能的的：存在在一一個(gè)個(gè)一一致致的的全全局局狀狀態(tài)態(tài)S，H的一一個(gè)個(gè)線線性性化化走走向向經(jīng)經(jīng)歷歷了了這這個(gè)個(gè)全全局局狀狀態(tài)態(tài)S，而而且且該該S使得得(s)為T(mén)rue。-明確確的的：對(duì)于于H的所所有有線線性性化化走走向向L，存存在在L經(jīng)歷歷的的一一個(gè)個(gè)一一致致的的全全局局狀狀態(tài)態(tài)S，而而且且該該S使得得(s)為T(mén)rue。分布布式式調(diào)調(diào)試試觀察察一一致致的的全全局局狀狀態(tài)態(tài)進(jìn)程程的的狀狀態(tài)態(tài)信信息息附附有有向向量量時(shí)時(shí)鐘鐘值值全局局狀狀態(tài)態(tài)的的一一致致性性判判斷斷———CGS條件件設(shè)S=(s1,s2,…,sN)是從從監(jiān)監(jiān)控控器器進(jìn)進(jìn)程程接接收收到到的的狀狀態(tài)態(tài)信信息息中中得得出出的的全全局局狀狀態(tài)態(tài)，，V(si)是從從pi接收收到到的的狀狀態(tài)態(tài)si的向向量量時(shí)時(shí)間間戳戳，，則則S是一一致致的的全全局局狀狀態(tài)態(tài)當(dāng)當(dāng)且且僅僅當(dāng)當(dāng)：：V(si)[i]>=V(sj)[i](i,j=1,2,……,N)即若若一一個(gè)個(gè)進(jìn)進(jìn)程程的的狀狀態(tài)態(tài)依依賴賴于于另另一一個(gè)個(gè)進(jìn)進(jìn)程程的的狀狀態(tài)態(tài)，，則則全全局局狀狀態(tài)態(tài)也也包包含含了了它它所所以以來(lái)來(lái)的的狀狀態(tài)態(tài)。。分布布式式調(diào)調(diào)試試全局局狀狀態(tài)態(tài)示示例例m1m2p1p2物理時(shí)間

CutC1(1,0)(2,0)(4,3)(2,1)(2,2)(2,3)(3,0)x1=1x1=100x1=105x2=100x2=95x2=90x1=90CutC2Sij=在進(jìn)程１發(fā)生事件i以及在進(jìn)程２發(fā)生事件j之后的全局狀態(tài)S00S10S20S21S30S31S32S22S23S33S43層次01234567分布布式式調(diào)調(diào)試試一致致全全局局狀狀態(tài)態(tài)網(wǎng)網(wǎng)格格分布布式式調(diào)調(diào)試試判定定可可能能的的從初初始始狀狀態(tài)態(tài)考考試試，，遍遍歷歷可可達(dá)達(dá)狀狀態(tài)態(tài)的的網(wǎng)網(wǎng)格格。。L:=0;States:={(s01,s02,……,s0N)};while(對(duì)所所有有可可能能的的S∈∈States，(s)=False)L:=L+1;Reachable:={S’’:H中從一一些S∈States可到達(dá)達(dá)的狀狀態(tài)∧∧level(S’)=L};States:=Reachable;endwhile輸出““可能能的”;

?

–層次012345FFFFTFF=((s)=False);T=((s)=True)分布式式調(diào)試試值判定定示例例在第５５層的的狀態(tài)態(tài)為T(mén)rue＝》明確的的在第第５層層的狀狀態(tài)為為False＝》可能的的分布式式調(diào)試試異步系系統(tǒng)開(kāi)銷(xiāo)很很大，，需要要作O(kＮ)次比較較。同步系系統(tǒng)物理時(shí)時(shí)鐘：：|Ci(t)－Cj(t)|<D，即在在范圍圍D內(nèi)同步步。同步系系統(tǒng)中中的算算法改改進(jìn)消息中中同時(shí)時(shí)攜帶帶物理理時(shí)間間戳和和向量量時(shí)間間戳測(cè)試條條件V(si)[i]≧≧V(si)[i]，且si和sj能在同同一時(shí)時(shí)間發(fā)發(fā)生第3章時(shí)時(shí)間和和全局局狀態(tài)態(tài)簡(jiǎn)介時(shí)鐘、、事件件和進(jìn)進(jìn)程狀狀態(tài)物理時(shí)時(shí)鐘同同步邏輯時(shí)時(shí)間和和邏輯輯時(shí)鐘鐘全局狀狀態(tài)分布式式調(diào)試試小結(jié)小結(jié)時(shí)鐘偏偏移和和時(shí)鐘鐘漂移移物理時(shí)時(shí)鐘同同步Cristian方法Berkeley方法網(wǎng)絡(luò)時(shí)時(shí)間協(xié)協(xié)議邏輯時(shí)時(shí)間發(fā)生在在先關(guān)關(guān)系Lamport時(shí)間戳戳向量時(shí)時(shí)鐘小結(jié)全局狀狀態(tài)一致割割集，，一致致全局局狀態(tài)態(tài)“快照照”算算法分布式式調(diào)試試狀態(tài)收收集判定可可能的的和明確的的作業(yè)11.411.14Databases-R-UsrunsaclusterofthreeserversA,B,andC,whichcommunicatewithoneanother.Youaretoldthatthecurrentclockskewsbetweenserverpairsareasfollows:A-B:3ms;B-C:1ms;C-A:-4ms.Further,youaretoldthatcorrectnessinthedatabaserequiresthatnotwoserverclocksbemorethan30msapart.Ifeachoftheservershasanabsoluteclockdriftof2msperminute,howmanyminimum(i.e.,worst-case)minutescantheclustergowithoutrunningasynchronizationalgorithmamongitsservers?作業(yè)a,b,andcareeventsandnotwoeventsbelongtothesameprocess.Proveordisprove(givecounter-example)thefollowing:(a)aisconcurrentwithbandbisbeforecimpliesthataisbeforec.(b)aisconcurrentwithbandbisconcurrentwithcimpliesthataisconcurrentwithc.9、靜夜四無(wú)鄰鄰，荒居舊業(yè)業(yè)貧。。1月-231月-23Sunday,January1,202310、雨中中黃葉葉樹(shù)，，燈下下白頭頭人。。。13:01:1513:01:1513:011/1/20231:01:15PM11、以我獨(dú)獨(dú)沈久，，愧君相相見(jiàn)頻。。。1月-2313:01:1513:01Jan-2301-Jan-2312、故人江海別別，幾度隔山山川。。13:01:1513:01:1513:01Sunday,January1,202313、乍乍見(jiàn)見(jiàn)翻翻疑疑夢(mèng)夢(mèng)，，相相悲悲各各問(wèn)問(wèn)年年。。。。1月月-231月月-2313:01:1513:01:15January1,202314、他鄉(xiāng)鄉(xiāng)生白白發(fā)，，舊國(guó)國(guó)見(jiàn)青青山。。。01一一月月20231:01:15下下午13:01:151月-2315、比不了了得就不不比，得得不到的的就不要要。。。一月231:01下午午1月-2313:01January1,202316、行動(dòng)出成成果，工作作出財(cái)富。。。2023/1/113:01:1513:01:1601January202317、做前，能夠夠環(huán)視四周；；做時(shí)，你只只能或者最好好沿著以腳為為起點(diǎn)的射線線向前。。1:01:16下午1:01下下午13:01:161月-239、沒(méi)有有失敗敗，只只有暫暫時(shí)停停止成成功?。?。1月-231月-23Sunday,January1,202310、很多事事情努力力了未必必有結(jié)果果，但是是不努力力卻什么么改變也也沒(méi)有。。。13:01:1613:01:1613:011/1/20231:01:16PM11、成功就是是日復(fù)一日日那一點(diǎn)點(diǎn)點(diǎn)小小努力力的積累。。。1月-2313:01:1613:01Jan-2301-Jan-2312、世間成事事，不求其其絕對(duì)圓滿滿，留一份份不足，可可得無(wú)限完完美。。13:01:1613:01:1613:01Sunday,January1,202313、不知知香積積寺，