Please use this identifier to cite or link to this item:
標題: 連通支配集合行動隨意式網路下協議問題之研究
The Anatomy Study of Agreement in Connected-Dominating-Set-Based Mobile Ad-hoc Networks
作者: 江茂綸
Chiang, Mao-Lun
關鍵字: Byzantine Agreement;拜占庭協議;Distributed System;Fault-tolerant;Consensus;Mobile Ad-hoc Network;Fault Diagnosis Agreement;Rule Based Diagnosis;CDS;Dominating set.;分散式系統;容錯能力;合議問題;隨意式網路;錯誤診斷協議;規則式偵錯;連通支配集合。
出版社: 資訊科學與工程學系所
引用: [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.
然而大部份的拜占庭協議問題,都要求正常的處理單元在相同的訊息交換次數中取得協議,這類型的拜占庭協議問題稱之為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.
其他識別: U0005-3107200820091800
Appears in Collections:資訊科學與工程學系所

Show full item record

Google ScholarTM


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.