- 學位論文
具權重考量之合議相關問題研究
Consensus Related Problems with Weight Consideration
摘要
在分散式系統中，工作之執行是透過多台電腦進行協同運算。然而，網路中可能存在著惡質性損毀之元件，因此對於系統之運算能力及結果之正確性皆會造成一定程度之影響。為了提供可靠的計算環境，系統本身應具備容錯機制。如此一來，當系統中的元件發生損毀，甚至遭受惡意攻擊時，依然能維持運算結果之正確。而上述問題可藉由合議問題的解決來達成，但由於傳統的合議問題有諸多的限制，缺乏彈性，並不適用於現今的許多應用中。因此，在本研究當中，我們將針對合議問題做一延伸及變型，重新定義出兩種新型態的合議問題。分別是 (1)具權重考量之k-set合議問題：透過結合傳統之k-set合議問題與權重的概念，允許每一個處理器提出多個初始值，並針對每個初始值設定權重，提升傳統合議問題之彈性，擴展其實用性。 (2)具權重考量之即時互動一致性問題：針對雲端運算之環境中，結合互動一致性問題與權重的概念，來解決一致性工作排程的問題。在此問題當中，將允許每一台伺服器可提出多個初始值，並對每個初始值設定其權重。在權重方面，將同時考量正權重以及負權重。透過我們所提出的演算法將可排除損毀元件之干擾，使網路中之伺服器可達成一致之執行順序，避免處理器對於資源之需求產生衝突而造成系統效率低下，以及可能產生死結之情形。另外，我們也提出適用於本問題之early stopping機制，提升演算法執行效率。當網路中的伺服器收集到足夠的訊息量時，可以提早結束訊息交換，達成互動一致性合議。
並列摘要
A fault-tolerant distributed system maintains normal operation as long as faulty components in the system are within a tolerable amount. To ensure that the system is robust, we need a mechanism to allow a set of processors to reach a common agreement, even in the presence of failures and malicious attacks. This problem can be solved as a consensus problem. However, conventional consensus problems have numerous limitations and lack flexibility and thus do not fit many modern applications. In this study, we attempt to extend the consensus problem by defining two new patterns of the consensus problem as follows: (1) k-set consensus problem with weight consideration of basis and multiple initial values: Each processor is allowed to have multiple initial values, and weight (basis) is considered in the k-set consensus problem; (2) early stopping interactive consistency problem with weight consideration: The early stopping concept and weight consideration will be introduced in the interactive consistency problem to solve the consistent task schedule problem under the cloud computing environment. If enough messages have been collected, the system can terminate message exchanging and achieve an interactive consistency earlier.