Abstract
在分散式互斥演算法則中，以法團結構（quorum structures)為基礎的演算法則是很重要的一種。此種演算法則能夠容忍因節點或網路鏈結失誤所引起的網路區隔 (network partitioning)，且通常僅引發較低的通訊負擔。此類演算法則的基本觀念描李述如下：一個節點在進入重要區段之前，必須取得某個法團（quorum）中之所有節點的允許（permission）。若我們能保証每一對的法團均有非空的交集，而且每一節點在任一時間只允許一個節點進入重要區段，則互斥很明顯的可以實現。根據不同的互斥需求，主要有三種法團結構在文獻中提出： coterie, wr-coterie 及k-coterie。它們分別應用在分散式互斥，備份資料(replicated data)一致性控制及k-互斥(k-mutual exclision)。在此論文中，我們提出新的方法以建構非支配性而且╱或是具有常數的期待法團大小（expected quorumsize）的coterie,wr-coterie及k-coterie。這些提出的方法可以很輕易的擴展而用以解決分散式互斥，備份資料（replicated data) 一致性控制或是k-互斥（k-mutual exclision）。非支配性法團結構是較為人們接受的，因為此類結構的達成最佳可存取率(avialability)的侯選者，在另一方面，具有常數的期待法團大小法團結構也是較為人們喜愛的，因為當我們所提出的方法用以解決上述問題時，其所需要的訊息負擔與法團大小是成正比的。我們亦對上述提出之方法在法團大小(quorum size)與法團可存取率 (quorum avaialability)方面作分析，並將分析結果與其他相關之方法作了詳細比較。Quorum-based algorithms are an important class of algorithms toachieve distributed mutual exclusion. They are resilient tonetwork partitioning caused by site and/or network linkfailures and usually evoke low communication cost. The basicidea of them is simple-a site should collect permissions(votes) from all sites of a quorum to enter the criticalsection. If we can assure that any pair of quorums have a non-empty intersection and each site gives its permission to onlyone site at a time, mutual exclusion is then guaranteed. Thecollection of quorums used by a quorum-based algorithm iscalled a quorum structure. According to different mutualexclusion scenarios, several types of quorum structures havebeen proposed: coterie, wr-coterie and k-coteries, which arerelated to distributed mutual exclusion, replicated dataconsistency and distributed k- mutual exclusion, respectively.In this dissertation, we propose novel methods for constructingcoteries, wr-coteries and k-coteries that are nondominated and/or of constant expected quorum size. The proposed methods caneasily be extended to solve the problems of mutual exclusion,replicated data consistency or k-mutual exclusion in adistributed system. Nondominated quorum structures arefavorable because they are candidates to achieve the optimalavailability, the probability that a quorum can be form in anerror-prone environment. On the other hand, quorum structuresof constant expected quorum size are preferable because whenthe proposed methods are applied to solve the problemsmentioned, the message cost is directly proportional to thequorum size.