樹與階層一致性演算法之分析

Abstract

樹與階層一致性演算法可以用來協調分散式系統上互相衝突的動作. 本論 文分析樹與階層一致性演算法之特性. 首先分析樹一致性演算法的可用 度 (availability) 並提出一個改良方法來增進一給定樹之效能. 接著 分析樹一致性演算法的訊息複雜度 (message complexity). 最後分析階 層一致性演算法的訊息複雜度. In a distributed system, conflicting operations to a shared resource must be synchronized to maintain consistency of the resuorce. Mutual exclusion and replica control are two examples. Tree quorum consensus (TQC) and hierarchical quorum consensus (HQC) are efficient solutions for mutual exclsuion and replica control, respectively. This dissertation studies the performance characteristics of TQC and HQC. First, the availability of TQC is characterized and a refinement algorithm is presented to improve the performance of a given tree structure. Then message complexities of TQC and HQC are analyzed. In addition, asymptotic analyses of the ratios of message complexity to quorum size for TQC and HQC are presented. It is shown that the ratios are convergent.