一個以Quorum為基礎的複本控制演算法

Abstract

在分散式系統中, 資料常被複製成多份儲存在不同的地方來增加容錯能 力, 複本控制演算法可以用來協調複製資料的一致性. 本篇論文提出一個 新的以quorum為基礎的複本控制演算法, 其特性為可適用於任意數目的複 本個數, 且能維持高availability的要求, 而quo-rum大小為 O(square root N); 再者, 我們的演算法是相當對稱的, 即每個節點所參與的 quorum個數幾乎是相同的. 最後在本文中會將我們的演算法與其它相關以 quorum為基礎的演算法做比較. We present a new quorum-based algorithm for managing replicated data. Existingalgorithms are designed to achieve high availability, but somehow they haverestrictions on the number of replicas. The primary goal of our design is tofind a protocol suitable for any number of replicas. Let N denote the numberof replicas in the system. The quorum size is O (square root N), which is thesame as grid protocol. Our protocol is also almost symmetric because each nodejoins almost the same number of quorums, i.e., each node takes nearly the sameresponsibility. A comparison between our algorithm and related quorum-basedones is also discussed.