(3.227.235.183) 您好!臺灣時間:2021/04/18 10:11
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:吳賦哲
研究生(外文):Wu, Fu-Che
論文名稱:以訊息關係為基礎的檢查點及回復演算法
論文名稱(外文):Checkpointing and Recovery Algorithms Based on Message Dependency
指導教授:黃廷祿
指導教授(外文):Ting-Lu Huang
學位類別:碩士
校院名稱:國立交通大學
系所名稱:資訊工程學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:1996
畢業學年度:84
語文別:中文
論文頁數:52
中文關鍵詞:檢查點回復一致發生在前鋸齒路徑訊息相關
外文關鍵詞:checkpointingrecoveryconsistenthappen beforezigzag pathmessage dependency
相關次數:
  • 被引用被引用:0
  • 點閱點閱:99
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
摘要
在分散式系統中,要提供系統具有發生錯誤後,可回復執行的能力,一般
可藉訊息登錄讓 系統可重複原來的執行,再回到錯誤發生之前。或藉檢
查點直接回到一致的系統狀態重新 執行。在我們論文中,我們首先介紹
四種可決定全域狀態是否一致的的關係:即鋸齒路徑 (Z)、發生在前(H)
、檢查點基礎的發生在前(CH)、和訊息相關(M)。這些關係中具有下列
的性質: Z > H > CH > M。M的集合最小,表示與某點有訊息關係的點最
少。在實作上, 只須在訊息上增加O(1)的訊息量便足以決定兩檢查點間
是否有訊息相關。我們的演算法以 訊息相關為基礎,所以,負擔很小。
接著,我們介紹作檢查點的演算法,對一不常發生錯 誤的系統而言,應
考慮採用在沒有錯誤發生時是較少負擔的作法,我們的演算法,將所有
的控制訊息都附在應用訊息之上。此外,為了維持各檢查點間的因果關係
,我們以訊息上 所帶檢查點的值,來判斷是否該作一檢查點。最後在回
復時,我們將由各檢查點的相關向 量,找出一組彼此間沒有訊息相關的
最大的一致全域檢查點。這樣的作法,不但不須要馬 上協調所須的額外
控制訊息,也不會有骨牌效應。缺點是作檢查點時須要較多的儲存空間,
及回復時須要O(N3)的時間去建構一致的檢查點。

abstract In distributed systems, failure recovery could be
achieved either by way ofmessage logging, with which we can
replay the original run to the state prior tofailure occurs, or
by way of checkpoting, with which we can directly rollback toa
consistent global checkpoints to start a new run. In our thesis,
we firstintroduce four relations, zigzag path(Z), happen before(
H),checkpoint-basedhappen before(CH) and message dependency(M),
to determine if the globalcheckpoints are consistent or not. The
relations have the following property:Z > H > CH > M. Set M is
smallest one. It means that the number of checkpointswhich have
message dependency with some checkpoint is least. As far
asimplementation is concerned, it only requires appending O(1)
additional messagesto each application message to determine if
the checkpoints have messagedependency with each other or not.
Our algorithm is based on message dependency;thus, the overhead
is small. Secondly, we present the checkpointing algorithm.In a
system, if a failure seldom occurs, we must choose an approach
with lessoverheads while the failure does not occur. In our
algorithm, all of the controlmessages are piggybacked on each
application message. Besides, to maintaincausal relation among
checkpoints, we use the value tagged on each message todecide
if checkpointing is required or not. Finally, in our recovery
algorithm,by comparing the dependency vector(DV), we can
construct a maximum globalcheckpoints without any message
dependency between them. Our algorithm does notneed extra
control message required in eager checkpoint coordination.
Inaddition, it is domino free. However this algorithm requires
more storages forcheckpointing and the time complexity for
recovery is O(N3).

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔