藉由線上建立因果角錐尋找一致全域檢查點

Abstract

尋找一分散式計算中的一致全域檢查點在許多分散式應用,如分散式測試 、除錯、及容錯計算中是一個中心問題。我們考慮的問題是利用因果角錐 來建構所有包含一給定區域檢查點集合 S 的一致全域檢查點。我們首先 提供一個藉由合併 S 中區域檢查點的因果角錐來建構 S 之因果角錐的機 制。之後,我們提供一個利用因果角錐尋找所有一致全域檢查點的演算法 。最後, 為簡化建構 S 之因果角錐之工作, 我們提供一個線上建構區域 檢查點之因果角錐的演算法。 Finding consistent global checkpoints of a given distributed computation is a central problem in many distributed applications, such as distributed testing,distributed debugging, and fault-tolerant computing. We consider the problem of constructing all consistent global checkpoints containing S, a set of local checkpoints, by using C-cone(S) (causally undered set with S). We first providea mechanism to generate the C-cone( S) by combining the C-cones of individual checkpoints in S. Then, an algorithm that uses C-cones to enumerate all consistent global checkpoints containing S is given. Finally, to facilitatethe construction of C-cone(S), we present an algorithm that generates C-conesof local checkpoints on-line.