臺灣博碩士論文加值系統

在分散式系統當中，如何達到系統的可靠度是一項非常重要的議題。而為了達成分散式系統中的容錯能力，每一個正常的處理單元在執行一些特定的任務時，必須事先達成一個共同的協議，以避免被其它遭受損毀而產生的錯誤的處理單元所影響。在分散式系統領域中，此問題稱之為拜占庭協議，同時這也是需要被注意的一環。一般來說，傳統的拜占庭協議都在良好的網路架構下做探討，像是全連接式網路及廣播式網路。然而近幾年的網路型態漸漸轉向無線式的網路架構，像是行動隨意式網路也愈來愈受到重視及歡迎，而這類型的網路特性就是可以動態的連結及移動。因此，必須在行動隨意式網路架構下重新檢視及探討傳統的拜占庭協議問題，以及與它相關的合協議問題。此外，本論文也同時探討處理單元及傳輸媒介同時發生不同損毀與影響程度的情況。
然而大部份的拜占庭協議問題，都要求正常的處理單元在相同的訊息交換次數中取得協議，這類型的拜占庭協議問題稱之為Immediate拜占庭協議。而允許參加者在不同的訊息交換次數中取得協議的另一種拜占庭協議方式，則稱之為Eventual拜占庭協議，Eventual拜占庭協議通常可以在f_act (f_act < f_m；f_act為實際發生惡性錯誤處理單元的個數; f_m為可容忍發生惡性錯誤處理單元的個數)次訊息交換後停止訊息交換。由此可知，Eventual拜占庭協議比Immediate拜占庭協議來得更有效率。而在本論文中，也將在隨意式網路下重新探討Eventual拜占庭協議，以期在忍容最大錯誤處理單元的分散式系統下，利用最少的訊息交換數，來求得協議值。
而為了使論文更加的完整，我們也探討了Fault Diagnosis Agreement (FDA)。 FDA的主要概念是使得每一個正常的處理單元可以各自偵測/定位出一個相同錯誤處理單元的集合。一般來說，當系統中存在很少量的錯誤處理單元時，FDA協定還是需要 [(k-1)/3] + 2 (k 代表網路中的處理單元個數)個執行次數去偵測/定位出錯誤的處理單元。然而，過多的訊息交換將會加重整個錯誤診斷協定的負擔。因此，本論文使用Evidence-based的FDA協定，利用最少個執行次數來提前找出錯誤的處理單元。更進一步，我們的協定也將偵測/定位出網路拓撲中最多的錯誤處理單元集合。

Reliability is an important research topic of distributed systems. To achieve fault-tolerance in the distributed systems, healthy processors need to reach a common agreement before performing certain special tasks, even if faults exist in many circumstances. This problem is called as the Byzantine Agreement (BA) problem and it must be addressed. In general, the traditional BA problem is solved in well-defined networks, such as a fully connected network or a broadcast network. However, the MANETs (Mobile Ad-hoc NETworks) are increasing in popularity and its network topology is dynamic in nature. Therefore, the BA problem and a closely related sub-problem, the Consensus problem, are re-examined in MANETs. Similarly, the dual failure mode on both processors and transmission media are considered in this dissertation.
Most BA problems require all the healthy processors to obtain an agreement at the same round; this kind of agreement is called an Immediate Byzantine Agreement (IBA). Another kind of agreement, Eventual Byzantine Agreement (EBA), allows its participants to reach a common agreement at different rounds when the f_act < f_m (f_act is the number of actual malicious faulty processors; f_m is the number of tolerate malicious faulty processors). As a result, EBA is more efficient than IBA. The EBA is also revisited in the MANET in this dissertation. Our protocol expects to use the minimum number of message exchanges to reach an agreement within the distributed system while tolerating the maximum number of faulty processors in MANETs.
As for the completeness, one important issue needs to be revised is the Fault Diagnosis Agreement (FDA). The goal of the FDA is to make each healthy processor able to detect/locate a common set of faulty processors. In general, the FDA protocol needs [(k-1)/3] + 2 (k is the number of processors in a network) rounds of message exchange to detect/locate the faulty components. However, the number of messages results in a large overhead in protocol. In this dissertation, the FDA problem is solved early by an evidence-based fault diagnosis protocol that uses the minimum number of rounds characterized by dual failure of processors. In addition, the proposed protocol can detect/locate the maximum number of faulty processors in a network.

摘要 ii
Abstract iv
List of Figures and Tables ix
List of Notations x
Chapter 1 Introduction 1
1.1. Problem Definition 1
1.2. Motivation 4
1.3. Organization of the Dissertation 5
Chapter 2 A Survey of Related Research Works 7
2.1 The Basic Assumptions of MANETs 7
2.2 Classification of Agreement Problems 10
2.3 Failure Types 13
2.3.1 Types of the Processor Failure 13
2.3.2 Types of the Transmission Media Failure 14
2.3.3 Generalized Failure 14
2.4 Early Stop Issue in Agreement Problem 15
2.5 Extension Application of Agreement Problem 16
Chapter 3 Basic Concepts and Approaches 19
Chapter 4 Protocol GCAP 24
4.1 The Number of Required Rounds for GCAP is Predictable in MANETs 24
4.2 The Number of Allowable Faulty Processors 25
4.3 The LMAJ Function, MAT Function, ic-tree(Ti), and VOTE Function Used in GCAP 30
4.4 The Procedure of Protocol GCAP 33
4.5 Example of GCAP 38
4.6 Concluding Remarks 50
Chapter 5 The Generalized Situation 52
5.1 The CCAP Protocol 53
5.1.1 Removing the Influence of Dormant Faulty Processors and Dormant Faulty Transmission Media 53
5.1.2 Removing the Influence of Malicious Faulty Transmission Media 54
5.1.3 Removing the Influence of Malicious Faulty Processor 54
5.2 The Procedure of CCAP Protocol 54
5.3 Examples of CCAP Protocol 59
5.4 Concluding Remarks 69
Chapter 6 The ESP Problem 70
6.1 The EDAP Protocol 70
6.2 The Example of EDAP Protocol 73
6.3 Concluding Remarks 83
Chapter 7 The Correctness and Complexity of CCAP and EDAP 84
7.1 Correctness 84
7.2 Complexity 90
Chapter 8 Extension to Fault Detection 95
8.1 The Concept and Principle of EFDA 95
8.2 The EFDA Protocol 100
8.2.1 The Message Collection Phase 100
8.2.2 The Dormant Diagnosis Process 100
8.2.3 The Malicious Diagnosis Phase 101
8.3 Example of Executing EFDA 103
8.4 The Correctness and Complexity of the EFDA 123
8.4.1 Correctness of EFDA 123
8.4.2 Complexity of EFDA 127
8.5 Concluding Remarks 128
Chapter 9. Conclusion and Future Works 130
Bibliography 133

[1]O. Babaglu, “On the reliability of consensus-based fault-tolerant distributed Computing systems,” ACM Transactions on Computing System, vol. 5, no.2, pp.394-416, 1987.
[2]O. Babaoglu and R. Drummond, “Streets of Byzantium: network architectures for fast reliable broadcasts,” IEEE Transactions on Data and Knowledge Engineering, vol. SE-11, no. 6, pp. 546-554, 1985.
[3]R. Baldoni, J. M. Hélary, M. Raynal, and L. Tangui, “Consensus in Byzantine asynchronous systems,” Journal of Discrete Algorithms, vol. 1, no. 2, pp. 185-210, 2003.
[4]A. Bar-Noy, D. Dolev, C. Dwork, and R. Strong, “Shifting gears: changing algorithms on the fly to expedite Byzantine agreement,” Information and Computation, vol. 97, no.2, pp.205-233, 1992.
[5]R. W. Buskens and R. P. Bianchini, “Distributed on-line diagnosis in the presence of arbitrary faults,” Proceedings of the Symposium on Fault-tolerant Computing, Toulouse, France, pp.470-479, 1993.
[6]V. Bharghavan and B. Das, “Routing in ad hoc networks using minimum connected dominating sets,” IEEE International Conference on Communications ’97, Montreal, Canada; pp. 376-380, June 1977.
[7]N. Deo, Graph theory with applications to engineering and computer science, Prentice-Hall, Englewood Cliffs, NJ, 1974.
[8]P. Dasgupta, “Agreement under faulty interfaces,” Information Processing Letters, vol. 65, no. 13, pp.125-129, 1998.
[9]D. Dolev, “The Byzantine generals strike again,” Journal of Algorithms, vol. 3, no. 1, pp. 14-30, 1982.
[10]D. Dolev and H. R. Strong, “Requirements for agreement in a distributed system,” Proceeding of the 2nd International Symposium on Distributed Data Bases, Berlin, pp. 115-129, 1982.
[11]D. Dolev and R. Reischuk, “Bounds on information exchange for Byzantine agreement,” Journal of ACM, vol. 32, no. 1, pp. 191-204, 1985.
[12]D. Dolev, R. Reischuk, and H. R. Strong, “Early stopping in Byzantine agreement,” Journal of ACM, vol. 37, no. 4, pp. 720-741, 1990.
[13]M. Fisher and N. Lynch, “A lower bound for the assure interactive consistency,” Information Processing Letters, vol. 14, no. 4, pp. 183-186, 1982.
[14]M. Fischer, N. Lynch, and M. Paterson, “Impossibility of distributed consensus with one faulty process,” Journal of ACM, vol. 32, no. 2, pp.374-382, 1985.
[15]M. Fischer, “The consensus problem in unreliable distributed systems (A Brief Survey),” Technical report, Department of Computer Science, Yale University, 2000.
[16]G. K. Gifford, “Weighted voting for replicated data,” Technical Report, CSL-79-14, XEROX Palo Alto Research Center, 1979.
[17]F. Halsall, Data communications, computer networks and open systems. 4th ed. Addison-Wesley Publishers, Massachusetts, USA, 1995.
[18]H. S. Hsiao, Y. H. Chin, and W. P. Yang, “Reaching fault diagnosis agreement under a hybrid fault model,” IEEE Transactions on Computers, vol. 49, no. 9, pp. 980-986, 2000.
[19]L. Lamport, “Lower bounds for asynchronous consensus,” Distributed Computing, vol. 19, no. 2, pp. 104.125, 2006.
[20]L. Lamport, R. Shostak, and M. Pease, “The Byzantine generals problem,” ACM Transactions on Programming Languages and Systems, vol. 4, no. 3, pp. 382-401, 1982.
[21]L. Lamport and P. M. Melliar-Smith, “Byzantine clock synchronization” ACM SIGOPS Operating Systems Review, vol. 20, no. 3, pp. 10-16, 1986.
[22]N. A. Lynch, M. J. Fischer, and R. J. Fowler, “A simple and efficient Byzantine generals algorithm,” Proceedings of 14th ACM Symposium on Theory of Computing, pp. 46-52, 1982.
[23]S. Mallela and G. M. Masson, “Diagnosis without repair for hybrid fault situations,” IEEE Transactions on Computers, vol. 29, no. 6, pp. 461-471, 1980.
[24]J. P. Martin and L. Alvisi, “Fast Byzantine consensus,” IEEE transactions on Dependable and Secure Computing, vol. 3, no. 3, pp. 202-215, 2006.
[25]J. M. McQuillan, I. Richer, and E. C. Rosen, “The new routing algorithm for ARPANET,” IEEE Transactions on Communications, vol. 28, no. 5, pp. 711-719, 1980.
[26]F. J. Meyer and D. K. Pradhan, “Consensus with dual failure modes,” IEEE Transactions on Parallel Distribute Systems, vol. 2, no. 2, pp.214-222, 1991.
[27]H. G. Molina, F. Pittelli, and S. Davidson, “Applications of Byzantine agreement in database systems,” ACM Transactions on Database Systems, vol. 11, no. 1, pp. 27-47, 1986.
[28]J. Moy, OSPF Version 2, Internet request for comments RFC 1247, July 1991.
[29]A. W. Krings and T. Feyer, “The Byzantine agreement problem: optimal early stopping,” Proceedings of 32nd Hawaii International Conference on System Sciences, Maui, Hi (USA), 1999.
[30]M. Kumar, L. Schwiebert, and M. Brockmeyer, “Efficient data aggregation middleware for wireless sensor networks,” Proceedings of 1st International Conference on Mobile, Ad-Hoc, and Sensor Systems, Ft. Lauderdale, Florida (USA), pp. 579-581, October 2004.
[31]M. Pease, R. Shostak, and L. Lamport, “Reaching agreement in presence of faults,” Journal of ACM, vol. 27, no.2, pp.228-234, 1980.
[32]K. J. Perry, Early stopping protocols for fault-tolerant distributed agreement, Ph. D. Thesis, Cornell University, January 1985.
[33]F. Preparata, G. Metze, and R. Chien, “On the connection assignment problem of diagnosable systems,” IEEE Transactions on Electronic Computers, vol. 16, no. 12, pp. 848-854, 1967.
[34]K. Shin and P. Ramanathan, “Diagnosis of processors with Byzantine faults in a distributed computing systems,” Proceedings of the Symposium on Fault-tolerant Computing, pp. 55-60, 1978.
[35]H. S. Siu, Y. H. Chin, and W. P. Yang, “A note on consensus on dual failure modes,” IEEE Transactions on Parallel and Distributed Systems, vol. 7, no. 3, pp. 225-229, 1996.
[36]H. S. Siu, Y. H. Chin, and W. P. Yang, “Byzantine agreement in the presense of mixed faults on processors and links,” IEEE Transactions on Parallel and Distributed Systems, vol. 9, no. 4, pp. 335-345, 1998.
[37]M. Steenstrup, Cluster-based network in ad hoc network, C.E. Perkins, ed., Addison-Wesley, 2001.
[38]H. Strong and D. Dolev, Byzantine Agreement. IBM Research Report, RJ-3714, Computer Science, 1982.
[39]R. Sivakumar, B. Das, and V. Bharghavan, “An improved spine-based infrastructure for routing in ad hoc networks,” Proceedings of the IEEE Symposium on Computers and Communications, 1998.
[40]I. Stojmenovic, M. Seddigh, and J. Xunic, “Dominating sets and neighbor elimination based broadcasting algorithms in wireless networks,” IEEE Transactions on Parallel and Distributed Systems, vol. 3, no.1, pp. 14-25, 2002.
[41]S. C. Wang, “A study of application of Byzantine agreement flight management system,” Proceedings of Aero. & Astro. Conference, AASRC, pp. 651-660, 1990.
[42]S. C. Wang, Y. H. Chin, and K. Q. Yan, “Byzantine agreement in a generalized connected network,” IEEE Transactions on Parallel and Distributed Systems, vol. 6, no.4, pp. 420-427, 1995.
[43]S. C. Wang, K. Q. Yan, and H. C. Hsieh, “The new territory of mobile agreement,” Computer Standards & Interfaces, vol. 26, no. 5, pp. 435-447, 2004.
[44]J. Wu, “Extended dominating set based routing in ad hoc wireless networks with unidirectional links,“ IEEE Transactions on Parallel and Distributed Systems, vol. 13, no. 9, pp. 14-25, 2002.
[45]K. Q. Yan and S. C. Wang, “Grouping Byzantine agreement,” Computer Standard & Interfaces, vol. 28, no. 1, pp. 75-92, 2005.
[46]K. Q. Yan and S. C. Wang, “Reaching fault diagnosis agreement on an unreliable general network,” Information Sciences, vol. 170, no. 2-4, pp. 397-407, 2005.
[47]K. Q. Yan, S. C. Wang, and Y. H. Chin, “Consensus under unreliable transmission,” vol. 69, no. 5, Information Processing Letters, pp.243-248, 1999.
[48]H. Yoshino, N. Hayashibara, and T. Enokido, “Byzantine agreement protocol using hierarchical groups,” Proceedings on 11th International Conference on Parallel and Distributed Systems, pp.64-70, July 2005.