標題: 樹與階層一致性演算法之分析
Performance Characterization of Tree and Hierarchical Quorum Consensus Algorithms
作者: 張禾坤
Her-Kun Chang
袁賢銘
Shyan-Ming Yuan
資訊科學與工程研究所
關鍵字: 分散式系統, 一致性, 可用度, 訊息複雜度;distributed systems, quorum consnesus, availability, message complexity
公開日期: 1993
摘要: 樹與階層一致性演算法可以用來協調分散式系統上互相衝突的動作. 本論
文分析樹與階層一致性演算法之特性. 首先分析樹一致性演算法的可用
度 (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.
URI: http://140.113.39.130/cdrfb3/record/nctu/#NT820394002
http://hdl.handle.net/11536/57897
顯示於類別:畢業論文