臺灣博碩士論文加值系統

在分散式系統中，工作之執行是透過多台電腦進行協同運算。然而，網路中可能存在著惡質性損毀之元件，因此對於系統之運算能力及結果之正確性皆會造成一定程度之影響。為了提供可靠的計算環境，系統本身應具備容錯機制。如此一來，當系統中的元件發生損毀，甚至遭受惡意攻擊時，依然能維持運算結果之正確。而上述問題可藉由合議問題的解決來達成，但由於傳統的合議問題有諸多的限制，缺乏彈性，並不適用於現今的許多應用中。因此，在本研究當中，我們將針對合議問題做一延伸及變型，重新定義出兩種新型態的合議問題。分別是 (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.

目錄
第一章 緒論 1
1.1 研究背景和動機 1
1.2 論文架構 6
第二章 相關研究 7
2.1 拜占庭協議問題與互動一致性問題之關聯性 7
2.2 權重式拜占庭協議問題 7
2.3 拜占庭協議問題：Optimal Early Stopping 10
2.4 k-set 合議問題 11
第三章 問題定義與系統環境 14
3.1 具權重考量之k-set合議問題 14
3.2 具權重考量之即時互動一致性問題 15
第四章 具權重考量之k-set合議問題演算法 19
4.1 資料結構：初始值 19
4.2 資料結構：kCP-tree 20
4.3 具權重考量之k-set合議演算法 21
4.4 模擬實例 24
4.5 演算法之正確性證明 29
第五章 具權重考量之即時互動一致性問題演算法 32
5.1 資料結構：ESIC-tree 32
5.2 提早結束機制 33
5.3 合議值計算機制：VoteESIC function 36
5.4 具權重考量之即時互動一致性演算法 37
5.5 模擬實例 42
5.6 效能評估 49
第六章 結論 55
參考文獻 56
附錄-英文論文 60

圖目錄
圖 1-1. 端運算服務架構 5
圖 3-1. 伺服器 si 及伺服器 sj 17
圖 4-1. 處理器 pi 之初始值 20
圖 4-2. kCPweight 演算法之執行程序 23
圖 4-3. k-set Consensus Protocol with weight consideration (kCPweight) 24
圖 4-4. 處理器 pA之初始值 25
圖 4-5. 處理器 pA之level 1 kCP-tree 26
圖 4-6. 處理器 pA之level 2 kCP-tree 27
圖 4-7. 處理器 pA之level 3 kCP-tree 27
圖 4-8. 處理器 pA之level 3 kCP-tree 多數決計算 29
圖 4-9. 處理器 pA加總後之矩陣 29
圖 5-1. 伺服器sk 之2-level ESIC-tree early stopping檢驗1 35
圖 5-2. 伺服器sk 之2-level ESIC-tree early stopping檢驗2 36
圖 5-3. VoteESIC 函式 37
圖 5-4. ESICweight 演算法之執行流程 40
圖 5-5. ESICweight 協定 41
圖 5-6. 伺服器 s1之1-level ESIC-tree(範例一) 43
圖 5-7. 伺服器 s1之2-level ESIC-tree(範例一) 45
圖 5-8. 伺服器 s1之3-level ESIC-tree(範例一) 45
圖 5-9. 伺服器 s1之1-level ESIC-tree(範例二) 47
圖 5-10. 伺服器 s1之2-level ESIC-tree(範例二) 48
圖 5-11. 成功通過early stopping機制所需之回合數以及未成功通過early stopping機制所需之回合數 50
圖 5-12. 無early stopping機制下所需之回合數以及具early stopping機制(且成功通過)所需之回合數 51
圖 5-13. 通過early stopping機制下所產生的節點數以及未通過early stopping機制下所產生的節點數 52
圖 5-14. 通過early stopping機制下所產生的節點數以及不具early stopping機制下所產生的節點數 52
圖 5-15. 不同比例之惡質性損毀伺服器下其early stopping條件檢測通過之次數 53

表目錄
表 4-1. 網路參數 25
表 4-2. 各個處理器之初始值 25
表 5-1. 各個伺服器之初始值(範例一) 42
表 5-2. 各個伺服器之初始值(範例二) 46

[1]F. N. Afrati and J. D. Ullman, "Optimizing Multiway Joins in a Map-Reduce Environment," Journal of the IEEE Transactions on Knowledge and Data Engineering, vol. 23, no. 9, 2011.
[2]H. Attiya, A. Bar-noy, D. Dolev, D. Koller, D. Peleg and R. Reischuk, "Achievable cases in an asynchronous environment," IEEE Symposium on Foundations of Computer Science, 1987.
[3]M. Barborak, M. Malek and A. Dahubra, "The Consensus Problem in Fault-Tolerant Computing," ACM Computing Surveys, Vol. 25, No. 2, pp. 171-220, 1993.
[4]P. Berman and J. A. Garay, "Asymptotically Optimal Distributed Consensus," Proceedings of the International Colloquium on Automata, Languages and Programming, pp. 80-94, 1989.
[5]P. Berman, J. Garay and K. Perry, "Towards Optimal Distributed Consensus," Foundations of Computer Science, pp. 410-415, 1989.
[6]M. Biely and M. Hutle, "Consensus when all processes may be Byzantine for some time," Theoretical Computer Science, 2010. (doi:10.1016/j.tcs.2010.11.012)
[7]E. Borowsky and E. Gafni, "Generalized FLP impossibility result for t-resilient asynchronous computations," Proceedings of the 25th annual ACM symposium on Theory of computing, pp. 91–100, 1993.
[8]S. Chaudhuri, M. Herlihy, N. Lynch and M. Tuttle, "Tight Bounds for k-set Agreement," Journal of the ACM, Vol. 47, No. 5, pp. 912-943, 2000.
[9]C.F. Cheng, S.C. Wang and T. Liang, "Byzantine Agreement Protocol & Fault Diagnosis Agreement for Mobile Ad-Hoc Network," Fundamenta Informaticae, vol. 89, no. 2, pp.161-187, 2008.
[10]C.F. Cheng, S.C. Wang and T. Liang, "The Anatomy Study of Server-initial Agreement for General Hierarchy Wired/Wireless Networks," Computer Standards and Interfaces, Vol. 31, No. 1, pp.219-226, January 2009.
[11]C. F. Cheng, S. C. Wang and T. Liang, "Investigation of Consensus Problem over Combined Wired/Wireless Network," Journal of Information Science and Engineering, Vol. 25, No. 4, pp. 1267-1281, July 2009.
[12]C.F. Cheng, S.C. Wang and T. Liang, "File Consistency Problem of File-Sharing in Peer-to-Peer Environment," International Journal of Innovative Computing, Information and Control, vol. 6, no. 2, pp.601-613, 2010.
[13]M. Fischer, "The consensus problem in unreliable distributed systems (a brief survey)," Lecture Notes in Computer Science, vol. 158, pp.127-140, 1983.
[14]M. Fischer, N. Lynch, and M. Paterson, "Impossibility of distributed consensus with one faulty process," Journal of the ACM (JACM), vol. 32, no. 2, pp. 378-382, 1985.
[15]M. Fisher and N. Lynch, "A lower bound for the time to assure interactive consistency," Information Processing Letters, vol.14, no.3, pp.183-186, 1982.
[16]V. K. Garg, J. Bridgman, "The Weighted Byzantine Agreement Problem," Proceedings of the IEEE Parallel & Distributed Processing Symposium, 2011
[17]D. Jiang, A. K. H. Tung, G. Chen, "MAP-JOIN-REDUCE: Toward Scalable and Efficient Data Analysis on Large Clusters," Journal of the IEEE Transactions on Knowledge and Data Engineering, vol. 23, no. 9, 2011.
[18]A. W. Kring and T. Feyer, "The Byzantine Agreement Problem: Optimal Early Stopping," Proceeding of the International Conference on System Sciences, 1999
[19]L. Lamport, R. Shostak, and M. Pease, "The Byzantine Generals Problem," ACM Trans. on Programming Languages and Systems, vol.4, no.3, pp.382-401, 1982.
[20]P. R. Parvedy, M. Raynal and C. Travers, "Decision Optimal Early-Stopping k-set Agreement in Synchronous Systems Prone to Send Omission Failures," Proceedings of the 11th Pacific Rim International Symposium on Dependable Computing, 2005.
[21]M. Pease, R. Shostak, and L. Lamport, "Reaching agreement in the presence of faults," Journal of ACM, vol. 27, no. 2, pp. 228–234, 1980.
[22]M. Roesch, "Snort-Lightweight Intrusion Detection for Networks," Proceeding of the 13th System Administration Conference, 1999.
[23]M. Saks and F. Zaharoglou, "Wait-free k-set agreement is impossible: The topology of public knowledge," SIAM J. Comput., Vol. 29, No. 5, pp. 1449–1483, 2000.
[24]A. Silberschatz, P. B. Galvin and G. Gagne: Operating System Concepts, 8th Ed., John Wiley & Sons, Inc, 2009
[25]S. C. Wang, K. Q. Yan and C. F. Cheng, "Asynchronous Consensus Protocol for the Unreliable Un-fully Connected Network," ACM Operating Systems Review, Vol. 37, No. 3, pp. 43-54, July 2003.
[26]S.C. Wang, K.Q. Yan and C.F. Cheng, "Efficient Multicasting Agreement Protocol," Computer Standards and Interfaces, Vol. 26, No. 2, pp. 93-111, March 2004.
[27]K.Q. Yan, Y.H. Chin, and S. C. Wang, "Optimal Agreement Protocol in Malicious Faulty Processors and Faulty Links, ” IEEE Transaction on Knowledge and Data Engineering, vol.4, no.3, June 1992