跳到主要內容

臺灣博碩士論文加值系統

(18.97.14.82) 您好!臺灣時間:2025/02/19 01:14
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:曹冠仁
研究生(外文):Kuan-Jen Tsao
論文名稱:拜占廷環境下複版控制法團之研究
論文名稱(外文):A Replica Control Protocol for Distributed Systems with Byzantine Faults
指導教授:邱舉明邱舉明引用關係
指導教授(外文):Ge-Ming Chiu
學位類別:碩士
校院名稱:國立臺灣科技大學
系所名稱:電機工程系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:1999
畢業學年度:87
語文別:中文
論文頁數:39
中文關鍵詞:法團群資料的一致性加強的鬆弛差集加強的鬆弛差對法團複版控制
外文關鍵詞:B-masking read-write coteriecoteriedata consistencyenhanced relaxed difference setenhanced relaxed difference pairquorumreplica control
相關次數:
  • 被引用被引用:0
  • 點閱點閱:309
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
在分散式系統中,資料複製是一個重要的課題,他能增加系統的容錯能力及運作效率。複版控制演算法提供了解決複製資料版本間不一致的問題。目前已有很多以法團(Quorum)為基礎的複版控制演算法之相關研究,其中包含了能容許拜占廷錯誤的法團系統。在目前已發展的拜占廷法團系統係針對如何將複製以結構化的安排達到降低法團大小,並確保資料的一致性。然而,大多數方法卻導致負載不平均及只能適用某些特定的資料複版數目的缺點。
在本篇論文中,我們利用加強的鬆弛差集及加強的鬆弛差對觀念,發展出一套能容許拜占廷錯誤的複版控制演算法之法團系統。它不但具有法團尺寸小的特性,而且對於任意數目的資料複版皆適用。此外,他也具有對稱的特性,也就是說在系統中每一個節點的重要性是一樣的。我們所提出的方法的另一個優點是可以允許調整相關的讀寫法團大小以適合分散式系統中不同讀出/寫入比率的需求。

Replica control has been an important issue for many applications in distributed systems. Replicated data objects not only provide high availability but also improve the performance of the system. One of the well-known replica control techniques is based on the employment of quorums, which are formed by grouping the replicated data objects in such a way that the consistency of the system can be ensured.
While many quorum-based protocols have been proposed for replica control, they are mostly restricted to tolerate faults that are fail-stop. Unfortunately, faults may be presented in more malicious manner. For example, some faulty processors may response to a request with an erroneous information without being detected. These faults are normally called Byzantine faults, On the other hand, existing protocols that are designed to handle Byzantine faults have some or all of the following drawbacks: 1. load is not evenly distributed among the replicated data sites, 2. do not apply to an arbitrary number of sites, and 3. do not allow the system to adapt to the read/write ratio of the systems.
In this thesis, we propose a replica control mechanism that can tolerate the Byzantine faults. The mechanism is based on the concept of enhanced relaxed difference pair, which is an extension of the enhanced relaxed difference set. In particular, we present a simple and efficient model for identifying enhanced relaxed difference pairs. This model eliminates the necessity of the time-consuming exhaustive search. It generates b-masking read-write coteries that are practically useful for an arbitrary number of sites in a distributed system. Unlike the previous methods, the model allows the flexibility of choosing appropriate read-write coteries that are most suitable for the target environment. Our mechanism is symmetric such that each site assume the same responsibility for the read/write operations with the existing methods.

第一章 緒論1
第二章 相關研究6
2.1 多數決定演算法6
2.2 演算法7
2.3 樹狀法團演算法7
2.4 階層式法團控制機制8
2.5 循環式法團機制8
2.6 拜占庭法團系統9
2.7 拜占庭法團方法10
第三章 拜占廷法團複製控制機制13
3.1 系統模式13
3.2 複製控制法團群14
3.3 加強的鬆弛差集16
第四章 B-MASKING READ-WRITE COTERIE的建制機制22
第五章 效能分析29
5.1對稱性29
5.2法團大小30
5.3各種方法的比較32
第六章 結論與未來工作34
6.1 結論34
6.2未來工作35
參考文獻36

[1] D. Agrawal and A. El Abbadi. “Exploting Logical Structures in Replicated Databases”. Information Processing Letters, 33(5):255-260, 1990.
[2] D. Agrawal and A. El Abbadi. “An Efficient and Fault-tolerant Solution for Distributed Mutual Exclusion”. ACM Transactions on Computer System, 9(1):1-20, Feb. 1991.
[3] Divyakant Agrawal, Ömer Egecioglu, Amr El Abbadi. “Billiard Quorums on the Grid”. Information Processing Letters 64(1): 9-16 (1997)
[4] P. Bernstein and N. Goodman. “The Failure and Recovery Problem for Replicated Databases”. In Proc. Second ACM Symp. Principles of Distributed Computing, pages 114-122, Aug. 1983.
[5] P.A. Bernstein, V. Hadzilacos, and N. Goodman. “Concurrency Control and Recovery in Database Systems”. Addision-Wesley, 1987. MA.
[6] S. Y. Cheung, M. H. Ammar, and M.Ahamad. “The Grid Protocol: A High Performance Scheme for maintaining Replicated Data”. IEEE Transactions on Knowledge and Data Engineering, 4(6):582-592, Dec. 1992.
[7] Cheng-Hong Cho and Jer-Tsang Wang. “Triangular Grid Protocol: An Efficient Scheme for Replica Control with Uniform Access Quorums”. In Euro-Par ’96 Parallel Processing Second International Euro-Par Conference Proceedings, pages 843-851, Aug. 1996.
[8] S. B. Davidson, H. Garcia-Molina, and D. Skeen. “Consistancy in Partitioned Networks”. ACM Computing Serveys, 17(3):341-370, Sep. 1985.
[9] H. Garcia-Molina and D. Barbara. “How to Assign Votes in a Distributed System”. Journal of the ACM, 32(4):841-860, Oct. 1985.
[10] D.K. Gifford. “Weighted Voting for Replicated Data”. In Proceedings of the 7th ACM Symposium on Operating System Principles, pages 150-159, 1979.
[11] Jehn-Ruey Jiang and Shing-Tsaan Huang, “Obtaining nondominated k-coteries for fault-tolerant distributed k-mutual exclusion”, Proceedings 1994 International Conference on Parallel and Distributed Systems, p. 582-7, 1994.
[12] Jehn-Ruey Jiang, Shing-Tsaan Huang and Yu-Chen Kuo. “Cohorts structures for fault-tolerant k entries to a critical section”, IEEE Transactions on Computers, Vol: 46, Iss: 2, p. 222-8, 1997.
[13] A. Kumar. “Hierarchical Quorum Consensus: A New Algorithm for Managing Replicated Data”. IEEE Transactions on Computers, 40(9):996-1004, Sep. 1991.
[14] Yu-Chen Kuo and Shing-Tsaan Huang, “An improvement of Maekawa’s mutual exclusion algorithm to make it fault-tolerant”. Parallel Processing Letters, Vol. 3, No. 3, p. 307-308, March 1993.
[15] Yu-Chen Kuo and Shing-Tsaan Huang, “A simple scheme to construct k-coteries with O(square root N) uniform quorum sizes", Information Processing Letters, Vol: 59, Iss: 1, p. 31-6, 1996.
[16] Yu-Chen Kuo and Shing-Tsaan Huang. "A geometric approach for constructing coteries and k-coteries", IEEE Transactions on Parallel and Distributed Systems, Vol: 8, Iss: 4 , p. 402-11, 1997.
[17] Yu-Chen Kuo and Shing-Tsaan Huang. "Recognizing nondominated coteries and wr-coteries by availability", IEEE Transactions on Parallel and Distributed Systems, Vol:9, Iss: 8, p.721-8, 1998.
[18] Ching-Min Lin, Ge-Ming Chiu, and Cheng-Hong Cho. “An Efficient Quorum-Based Scheme for Managing Replicated Data in Distributed Systems”,In Proceedings of International Conference on Parallel Processing ,1999.
[19] Wai-Shing Luk and Tien-Tsin Wong. “Two New Quorum Based Algorithms for Distributed Mutual Exclusion”. In Proceedings of Int’l Conf. on Distributed Computing Systems, pages 100-106, May 1997.
[20] Jr. Marshall Hall. “Combinatorial Theory”. John Wiley and Sons, 1986, Chapter 11.
[21] N. C. Mendonca and R. O. Anido. “Using Extended Hierarchical Quorum Consensus to Control Replicated Data: from Traditional Voting to Logical Structures”. In Proceedings of the 27th Annual Hawaii International Conference on System Science, pages 303-312, 1994.
[22] M. Maekawa, “A N0.5 Algorithm for Mutual Exclusion in Decentralized System”. ACM Trans. Computer System, 3(1985) 145-159.
[23] D. Malkhi and M. Reiter. “Byzantine Quorum Systems”.In Proceedings of the 29th ACM Symp. Theory of computing, May 1997.
[24] D. Malkhi, M. Reiter and A. Wool. “The Load and Availability of Byzantine Quorum Systems”.In Proceedings of the 16th Annual ACM Symposium on the Principles of Distributed Computing, August 1997.
[25] M. L. Neilsen, M. Misuno, and M.Raynal. “A General Method to Define Quorums”. In Proceeding of the 12th International Conference on Distributed Computing Systems, pages 657-664, 1992.
[26] Wee K. Ng and Chinya V. Ravishankar. “Coterie Templates: A New Quorum Construction Method”. ICDCS 1995: 92-99.
[27] David Peleg and Avishai Wool, “Crumbling walls: a class of practical and efficient quorum systems”, Distributed Computing, Vol 10, p. 87-97, 1997.
[28] R. Schlichting and F. Schneider. “Fail-stop Processors”. ACM Transactions on Computer Systems, 1:303-312, 1994.
[29] R. H. Thomas. “A majority Consensus Approach to Concurrency Control for Multiple Copy Databases”. ACM Transactions on Database Systems, 4(2):180-209, Jun, 1979.
[30] Chienwen Wu. “A Fault Tolerant O(N0.5) Algorithm for Distributed Mutual Exclusion”. In The 20th Annual International Phoenix Conference on Computers and Communications, pages 175-180, 1993.
[31] Y. T. Wu, Y. J. Chang, S.M. Yuan, and H. K. Chang. “A New Quorum-Based Replica Control Protocol”. In Proceeding. Pacific Rim International Symposium on Fault-tolerant Systems, pages 116-121, Dec. 1997.

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top