跳到主要內容

臺灣博碩士論文加值系統

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

詳目顯示

我願授權國圖
: 
twitterline
研究生:林世宏
研究生(外文):Shih-Hung Lin
論文名稱:環形編號系統之資料複版控制
論文名稱(外文):A Circular Numbering Approach for Replica Control
指導教授:卓政宏
指導教授(外文):Cheng-Hung Cho
學位類別:碩士
校院名稱:國立臺灣科技大學
系所名稱:電機工程系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:1999
畢業學年度:87
語文別:英文
論文頁數:30
中文關鍵詞:法團選舉人投票環形彈性
外文關鍵詞:QuorumElectoral VotingCircular Spring
相關次數:
  • 被引用被引用:0
  • 點閱點閱:198
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
摘 要
在分散式系統中,資料複製是一個很重要的課題,它能增加系統的容錯能力及運轉效率。複版控制演算法提供了解決複製資料版本不一樣問題,複版資料管理的限制是執行時任兩個寫入作業間或一對讀,寫作業間都必須使用至少一個共同資料版。如此,則不但任何讀出作業都可以得到最新版的資料,所有寫入作業間互相衝突的問題也可以避免了,整個系統好像一個單獨版本的系統一般。
大部分複板版控制的演算法都是以法團為基礎,它們將複製的資料安排在一些像樹狀、方格網狀、三角格網狀等邏輯結構上,這些方法都是為了降低法團的大小,提高容錯率,或者是平均負載,但是,大部分無法達到所有目標,因為優先權的考量不一樣。所以,這些方法可能有一些缺點,如負載不平均或只適用於某些特定節點數目。
本篇論文中,我們利用環狀結構為基礎,提出了兩個方法:選舉人投票協定及環狀彈性協定。這兩個方法都是對稱的,也就是說在系統中每個節點的負載是一樣的。另外,它們都可適用於個各種數目的節點,且它們的容錯率是很高的。

Abstract
Data replication is an important technique in distributed system. Most replication techniques are quorum-based approaches. These approaches employ logical structures or mathematical methods to solve the replication problem. They attempt to get smaller quorum size, higher availability, and better loading balance. However, it is very hard to be successful at all aspects because every approach has its priority. They may have some of the following disadvantages: (1) The load of every site in the distributed system is unbalance. (2) These methods do not applied to an arbitrary number of sites. These motivate us to design a protocol to improve the problems.
In this thesis, we propose two protocols: electoral voting protocol and circular spring protocol. They are based on a circular numbering system. A distributed system with N nodes is organized as a logical circle, denoted by N-ring. Our protocols are symmetric that each site bears the same responsibility. They are applied to arbitrary number of sites. And the availability of our protocols is better than most protocols.

Contents
1 Introduction 1
2 Related Works 3
2.1 Read-one-write-all Protocol………………………………… 3
2.2 Weighted Voting Protocol…………………………………... 3
2.3 Grid Protocol………………………………………………... 4
2.4 Triangular Grid Protocol……………………………………. 5
2.5 Circle Grid Protocol………………………………………… 6
2.6 RW-Difference Pair Protocol……………………………….. 7
3 Electoral Voting Protocol 9
3.1 Definitions…………………………………………………… 9
3.2 Our Protocol………………………………………………….11
3.3 Proof of Correctness………………………………………….14
4 Circular Spring Protocol16
4.1 Definitions……………………………………………………16
4.2 Our Protocol………………………………………………….17
4.3 Proof of Correctness………………………………………….19
5 Performance Analysis21
5.1 Symmetric Property…………………………………………..21
5.2 Quorum Size………………………………………………….22
5.3 Availability……………………………………………………23
5.4 A Comparison………………………………………………...24
6 Conclusions28

References
[1] D. Agrawal and A. El Abbadi, “The Tree Quorum Protocol: An Efficient Approach for Managing Replicated Data”, in Proc. of Very Large Database Conf., pp. 243 ~ 254, 1990.
[2] D. Agrawal and A. El Abbadi, “The Generalized Tree Quorum Protocol: An
Efficient Approach for Managing Replicated Data”, ACM Trans. Database
syst.17(4), pp. 689 ~ 717, 1992.
[3] S. Y. Cheung, M. H. Ammar, and M. Ahamad, “The Grid Protocol: A High Performance Scheme for Maintaining Replicated Data,” in Proc. of the IEEE 6th Int. Conf. on Data Engineering, pp. 438 ~ 445, 1990.
[4] C. Wu and G. G. Belford, “The Triangular Lattice Protocol: A Highly Fault Tolerant and Highly Efficient Protocol for Replicated Data”, in IEEE 11th Proc. Symp. on Reliable Distributed System, pp. 66 ~ 73, 1992.
[5] C. H. Cho and J. T. Wang, “Triangular Grid Protocol: An Efficient Scheme for Replica Control with Uniform Access Quorums,” in Lecture Notes in Computer Sciences, pp.843-851(EI)5, 1996.
[6] G. M. Chiu, C. M. Lin, and C. H. Cho, “An efficient Quorum-Based Scheme for Managing Replicated Data in Distributed system”, in Proc. of the Int. Conf. on Parallel Processing, 1999.
[7] D.K. Gifford, “Weighted Voting for Replicated Data,” in Proc. of the 7th ACM Symp. on Operating System Principles, pp. 150 ~ 159, 1979.
[8] A. Kumar, M. Robinovich, and R. Sinha, “A Performance Study of a New Grid protocol and General Grid Structures for Replicated Data,” Tech. Report 93-03-02, Department of Computer Science and Engineering, University of Washington, March 1993.
[9] A. Kumar, M. Robinovich, and R. Sinha, “A Performance Study of General Grid Structures for Replicated Data,” in Proc. of the IEEE 13th Int. Conf. on Distributed Computing System, pp. 178 ~ 185, 1993.
[10] Y. T. Wu, Y. J. Chang, S. H. Yuan, and H. K. Chang, “A New Quorum-Based Replica Control Protocol,” in Proc. Pacific Rim Int. Symp. on Fault-tolerant System, pp. 116 ~ 121, Dec. 1997.
[11] R.H. Thomas, “A Majority Consensus Approach to Concurrency Control for Multiple Copy Database”. ACM Trans. on Database System, 4(2): 180 ~ 209, Jun. 1979.
[12] Marshall Hall Jr., “Combinatorial Theory”. John Wiley and Sons, 1986. Chapter 11.
[13] W. S. Luk and T. T. Wong, “Two New Quorum Based Algorithms for Distributed Mutual Exclusion”, In Int. Conf. On Distributed Computing System, pp. 100 ~ 106, May 1997.

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關論文