臺灣博碩士論文加值系統

近年來由於無線通訊以及行動計算的蓬勃發展使得現今的網路型態走向了混合式的網路（包含了有線網路及無線網路）。因此混合式網路的可靠度以及容錯問題成為非常重要的課題。 為了提供可靠的計算環境，我們需要一個機制讓參與運作的處理器即使在發生錯誤或攻擊時仍能夠達成協議。 因此拜占庭協議問題以及合議問題成為許多學者們關注的焦點。 然而，過往的拜占庭協議問題以及合議問題的研究大都是針對在有線的網路之上。由於有線網路的實體拓樸為靜態的，使得過往針對這些固定式網路所提出的協定無法運作在混合式網路之中，其主要原因在於混合式網路之實體拓樸為動態的。
在本論文中，我們將探討拜占庭協議問題以及合議問題於混合式網路。為了因應混合式網路的特性（行動式處理器的運算能力通常較固定式處理器要來的弱）以及減少為了達成協議所需要的訊息交換次數，因此在我們所設計的協定之中導入了階層式的概念，將大部分的通訊工作以及運算工作交由伺服器來處理，如此一來將可以大幅降低行動式處理器的負擔。以效能的觀點來看，本論文中所提出的協定使用了最少的訊息交換次數並且可以容忍最大數量的損毀處理器。此外，由於純粹的有線網路以及純粹的無線網路都是混合式網路的特例，因此我們也將討論協議問題於這兩種網路之上。
為了提供更高可靠度的計算環境，我們還必須偵測/定位出網路中的損毀處理器。 因此，我們也將提出一個新的錯誤診斷協定來偵測/定位出損毀的處理器於混合式網路之中。a
在應用方面，近年來檔案分享已經成為點對點網路上最受歡迎的一項服務，而許多的點對點網路都是架構在有線及無線的混合式網路之上。這也使得檔案一致性的問題成為一項非常重要的課題。 因為惡質性損毀的攻擊者可能會隨意變更檔案的內容，並且將這些更改過的檔案傳送給其他的處理器。如此一來將使網路上充斥著不一致的檔案，造成浪費許多的資源，例如：頻寬、儲存空間以及傳輸時間。 因此確認所擁有的檔案是否為正確是相當重要的。 在本研究當中我們將使用所提出的協定來解決檔案一致性的問題於點對點網路之中。

Since wireless communication and mobile computing are becoming more and more ubiquitous, most network environments today are combined wired and wireless. The reliability and fault tolerance of the combined wired/wireless network has become an important topic. In order to provide a reliable environment, a mechanism that allows a set of processors to reach a common agreement, even in the presence of faulty processors, is needed. Therefore, the Byzantine Agreement (BA) problem and Consensus problem have drawn attention of more researchers. Traditionally, most of the BA problem and Consensus problem were focused on wired networks. We know that the physical topology of a wired network is static, but the physical topology of a combined wired/wireless network is dynamic. Thus, previous BA and Consensus protocols for static network are not applicable in a combined wired/wireless network.
In this dissertation, we visited the BA problem and Consensus problem in combined wired/wireless network. In order to meet the characteristics of combine wired/wireless networks (the limited resources have made the computation ability of mobile processors often weaker than that of stationary processors) and reduce the number of rounds of message exchange required, most of the communications and computation overhead must be fulfilled within by the servers. Therefore, we introduce a hierarchical concept in our system model. Only servers need to exchange messages and compute the common value. From the performance perspective, the proposed protocols use the minimum number of message exchanges and can tolerate the maximum number of faulty processors allowed in the networks. AS a matter of fact, pure wired networks and pure wireless networks are all special case of the combined wired/wireless networks. We also discuss the BA and Consensus problems in pure wired network and pure wireless network.
In a highly reliable fault-tolerant environment, to reach a common agreement is not enough. It is also necessary to detect/locate the faulty components in the network. Therefore, we also propose a new protocol to solve the Fault Diagnosis Agreement (FDA) problem in combined wired/wireless networks.
In the usage, the file-sharing application has been the most popular application in Peer-to-Peer (P2P) systems. Many P2P networks are overlay networks because they run on top of the combined wired/wireless network. Hence, the Consensus problem of file-sharing has become an important topic. As malicious attackers may modify files arbitrarily and spread inconsistent files to other processors in the P2P network, inconsistent files will not only spread in P2P networks but also waste resources, such as bandwidth, space of storage and transmission time. Hence, how to make fault-free processors ensure that the files they hold are correct is an import topic. In this thesis, we give an application of Consensus protocol to ensure the file consistency of file-sharing in P2P systems.

ABSTRACT iii
ACKNOWLEDGEMENT v
TABLE OF CONTENTS vi
LIST OF FIGURES ix
LIST OF TABLES xi
LIST OF NOTATIONS xii
Chapter 1 Introduction 1
1.1 Problem Definition 1
1.2 Motivation 2
1.3 Organization of Dissertation 3
Chapter 2 A Survey of Related Research Works 4
2.1 Network Structures 4
2.1.1 Pure Wired Network 4
2.1.2 Pure Wireless Network 6
2.1.3 Combined Wired/Wireless Network 7
2.2 The Fallible Components 8
2.2.1 The Symptoms of a Faulty Processor 8
2.2.2 The Symptoms of a Faulty Communication Link 8
2.3 Agreement Problems Definition 9
2.3.1 Byzantine Agreement Problem 9
2.3.2 Consensus Problem 13
2.3.3 Fault Diagnosis Agreement Problem 16
2.4 Conclusion 19
Chapter 3 Basic Concepts and Approaches 20
3.1 Agreement Problem in Pure Wireless Network 21
3.2 Agreement Problem in Combined Wired/Wireless Network 22
3.2.1 Byzantine Agreement Problem in Combined Wired/Wireless Network 23
3.2.2 Consensus Problem in Combined Wired/Wireless Network 24
3.3 Fault Diagnosis Agreement Problem in Combined Wired/Wireless Network 26
3.4 File Consistency Problem of File-Sharing in Peer-to-Peer Systems 27
Chapter 4 Byzantine Agreement Protocol for Wireless Networks 29
4.1 The Conditions for BA Problem in Wireless Network 29
4.1.1 System Model 29
4.1.2 The number of Message Exchange Rounds Required by MAHAP 30
4.1.3 Constraint 30
4.2 Proposed BA Protocol: “Mobile Ad-Hoc Agreement Protocol” (MAHAP) 31
4.2.1 Message-Exchanging Phase 31
4.2.2 Decision-Making Phase 32
4.2.3 Extension-Agreement Phase 33
4.2.4 The Message Gathering Tree (mg-tree) 36
4.2.5 The Information Collecting Tree (ic-tree) 37
4.3 An MAHAP Execution Example 37
4.4 The Correctness and Complexity of MAHAP 43
4.5 Conclusion 47
Chapter 5 Server-initiated Agreement Protocol for Combined Wired/Wireless Networks 49
5.1 The Conditions for BA Problem in Combined Wired/Wireless Network 49
5.1.1 System Model 49
5.1.2 Properties of the BA Problem 50
5.1.3 Constraint 51
5.2 Secure Communication 51
5.2.1 Related Cryptographic Technologies 51
5.2.2 Approach 53
5.3 BA Protocol: “Server-initiated Byzantine Agreement Protocol” (SBAP) 53
5.3.1 The Number of Required Rounds of Message-Exchange 54
5.3.2 Message-Exchanging Phase 54
5.3.3 Decision-Making Phase 55
5.3.4 Agreement-Distribution Phase 55
5.4 An Example of Reaching Byzantine Agreement 57
5.5 The Correctness and Complexity of SBAP 58
5.6 Conclusion 61
Chapter 6 Client-initiated Consensus Protocol for Combined Wired/Wireless Networks 63
6.1 The Conditions for Consensus Problem in Combined Wired/Wireless Network 63
6.1.1 System Model 63
6.1.2 Properties of the Consensus Problem 65
6.1.3 Constraint 65
6.2 Transmission Protocol: “Secure Relay Fault-tolerance Channel” (SRFC) 66
6.2.1 The Connectivity Constraint 67
6.2.2 Four Cases of Fault Handling 68
6.3 Consensus Protocol: “Client-initiated Consensus Protocol” (CCP) 69
6.3.1 Client-initiated Stage 70
6.3.2 Consensus Stage 72
6.4 An Example of Reaching Consensus 74
6.4.1 Client-initiated Stage 74
6.4.2 Consensus Stage 75
6.5 The Correctness and Complexity of CCP 77
6.6 Conclusion 79
Chapter 7 Fault Diagnosis Agreement 81
7.1 Proposed Protocol: “Adaptive Fault Diagnosis Agreement Protocol” (AFDA) 81
7.1.1 Message-Collection Phase 82
7.1.2 Fault-Diagnosis Phase 82
7.1.3 Re-configuration Phase 84
7.2 An AFDA Execution Example 86
7.2.1 Message-Collection Phase 87
7.2.2 Fault-Diagnosis Phase 87
7.2.3 Re-configuration Phase 87
7.3 The Correctness of AFDA 91
7.3.1 AFDA with MAHAP in Wireless Network 91
7.3.2 AFDA with SBAP in Combined Wired/Wireless Network 93
7.4 Conclusion 95
Chapter 8 Consensus Problem under Peer-to-Peer Environment: An Application to File-Sharing 96
8.1 Introduction 97
8.1.1 The Classification of Peer-to-Peer File-Sharing Systems 97
8.1.2 Clustering Algorithm 98
8.2 System Model and Approach 99
8.2.1 Clustering Algorithm: K-means Algorithm 99
8.2.2 Consistent Hash Function: SHA-1 Function 101
8.2.3 Overlay Network: de-Bruijn Graph 101
8.2.4 Consensus Protocol: Consensus Protocol for P2P Network (CPp2p) 103
8.3 An CPp2p Execution Example 107
8.3.1 Clustering 107
8.3.2 Mapping the Processors in Cluster to de-Bruijn Overlay Network 107
8.3.3 Getting the Consistent File Information 108
8.4 The Correctness of CPp2p 113
8.5 Conclusion 114
Chapter 9 Conclusion and Future Work 116
9.1 Conclusion 116
9.2 Future Work 117
Bibliography 119

[1] J. C. Adams and K.V.S. Ramarao, “Distributed diagnosis of Byzantine processors and links,” Proceeding of the Symposium on Distributed Computing Systems, pp.562-569, 1989.
[2] J. Aspnes, Z. Diamadi, and G. Shah, “Fault-Tolerant Routing in Peer-to-Peer Systems,” in Proceeding of the 23rd Annual Symposium on Principles of Distributed Computing, pp.223-232 ,2002.
[3] O. Babaoglu, and R. Drummond, “Streets of Byzantium: Network Architectures for Fast Reliable Broadcasts,” IEEE Transactions on Software Engineering, Vol. 11, no. 6, 1985, pp. 546-554.
[4] A. Bar-Noy, D. Dolev, C. Dwork and H. 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] 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.
[6] B. Bellur and R. G. Ogier, A Reliable, “Efficient Topology Broadcast Protocol for Dynamic Networks,” Proceeding of the 18th IEEE INFOCOM, pp.178-186, 1999.
[7] W. G. Bridges and S. Toueg, “On the Impossibility of Directed Moore Graphs,” Journal of Combinatorial Theory, no. 3, 1980.
[8] D. R. Broug, Logic Programming. New Frontiers, Kluwer Academic, 1992.
[9] T. Camp, J. Boleng, and V. Davies, “A Survey of Mobility models for Ad Hoc Network Research,” Wireless Communications & Mobile Computing, vol. 2, no. 5, 2002.
[10] T. Chandra and S. Toueg, “Unreliable Failure Detectors for Reliable Distributed Systems,” Journal of the ACM, Vol. 43, No. 4, 1996, pp. 225-267.
[11] B. Cohen, “Incentives Build Robustness in BitTorrent,” Proceeding of the Workshop on Economics of Peer-to-Peer Systems, pp.1-5, 2003.
[12] G. Coulouris , J. D. Dollimore, T. Kindberg, “Distributed Systems-Concepts and Design”,3rd Edition, Addison-Wesley 2001.
[13] G. D. Crescenzo, R. Ge and G. R. Arce “Securing Reliable Server Pooling in MANET Against Byzantine Adversaries,” IEEE Journal on Selected Areas in Communications, vol. 24, no. 2, 2006, pp. 357-369.
[14] J. Daemen, V. Rijmen, “The Rijndael Block Cipher,” AES Document Version2.
[15] D. Dolev, R. Reischuk, and A.R. Strong, “Early Stopping in Byzantine Agreement,” ACM for Computing Machinery, vol. 37, no. 4, pp.720-741, 1990.
[16] W. Diffie and M. E. Hellman, “New Directions in Cryptography,” IEEE Transactions on Information Theory, vol.22, pp. 644-654, 1976.
[17] M. Feldman, K. Lai, I. Stoica, and J. Chuang, “Robust Incentive Techniques for Peer-to-Peer Networks,” Proceeding of the 5th ACM Conference on Electronic Commerce, pp.102-111, 2004.
[18] FIPS 180-1. Secure Hash Standard. U.S. Department of Commerce/NIST, National Tehnical Information Service, Springfield, VA, Apr. 1995.
[19] M. Fisher, and N. Lynch, “A Lower Bound for the Assure Interactive Consistency,” Information Processing Letters, vol.14, no.3, pp.183-186, 1982.
[20] Gnutella, http://www.gnutella.com
[21] R. Guerraoui and A. Schiper, “The Generic Consensus Service,” IEEE Transactions on Software Engineering, vol. 27, no. 1, 2001, pp. 29-41.
[22] X. Hong, K. Xu, and M. Gerla, “Scalable routing Protocols for Mobile Ad Hoc Networks,” IEEE Network, vol. 16, no.4, pp.11-21, 2002.
[23] H.S. Hsiao, Y.H. Chin, W.P. Yang, “Reaching Fault Diagnosis Agreement under a Hybrid Fault Model,” IEEE Transactions on Computers, vol. 49, no. 9, pp.980-986, 2000.
[24] P. Jacquet, P. Muhlethaler, T. Clausen, A. Laouiti, A. Qayyum and L. Viennot, “Optimized Link State Routing Protocol for Ad Hoc Networks,” Proceedings of IEEE International Technology for the 21st Century, 2000.
[25] D. B. Johnson and D. A. Maltz, Dynamic Source Routing in Ad Hoc Wireless Networks, Mobile Computing, Kluwer, 1996.
[26] L. Kaufman and P. J. Rousseeuw, finding Groups in Data: An Introduction to Cluster Analysis, John Wiley & Sons, Inc., New York, 1990.
[27] A. W. Krings and T. Feyer, “The Byzantine Agreement Problem: Optimal Early Stopping,” Proceedings of 32nd Hawaii International Conference on System Sciences, LNCS 520, 1999.
[28] 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.
[29] D. Loguinov, A. Kumar, V. Rai, and S. Ganesh, “Graph-Theoretic Analysis of Structured Peer-to-Peer Systems: Routing Distances and Fault Resilience,” Proceeding of Applications, technologies, architectures, and protocols for computer communications, pp.395-406, 2003.
[30] S. Mallela and G. M. Masson, “Diagnosable systems for intermittent faults,” IEEE Transaction on Computers, vol. 27, no. 6, pp. 560-566, 1978.
[31] N. Malpani, J. L. Welch and N. Vaidya, “Leader election algorithms for mobile ad hoc networks,” Proceedings of the 4th International workshop on Discrete algorithms and methods for mobile computing and communications, pp.96-103, 2000.
[32] S. Marano, V. Matta and L. Tong, “Distributed inference in the presence of Byzantine sensors,” Proceedings of IEEE Asilomar Conference on Signals, Systems, and Computers, 2006, pp. 281-284.
[33] F.J. Meyer and D.K. Pradhan, “Consensus with Dual Failure Modes,” IEEE Transaction on Parallel and Distributed Systems, vol. 2, no. 2, pp. 214-222, 1991.
[34] Napster, http://www.napster.com
[35] M. Naor and U. Wieder, “A Simple Fault Tolerant Distributed Hash Tables,” Lecture Notes in Computer Science, vol. 2735, pp. 88-97, 2003.
[36] M.R. Pearlman and Z. J. Haas, “Determining the optimal configurations for the zone routing protocol,” IEEE Journal on Selected Areas in Communications, vol.17, no. 8, pp.1395–1414, 1999.
[37] 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.
[38] G. Pei, M. Gerla, and T.W. Chen, “Fisheye State Routing: A Routing Scheme for Ad Hoc Wireless Network,” Proceedings of the IEEE International Conference on Communications, pp.70-74, 2000.
[39] C.E. Perkins, Ad Hoc Networking, Addison-Wesley, 2001.
[40] C.E. Perkins and E. M. Royer, “Ad-Hoc On-Demand Distance Vector Routing,” Proceedings of the 1st IEEE Workshop on Mobile Computing Systems & Applications, pp.90–100, 1999.
[41] G. Rabbat, D. Nowak and A. Bucklew, “Generalized Consensus Computation in Networked Systems with Erasure Links,” Proceedings of IEEE 6th Workshop on Signal Processing Advances in Wireless Communications, 2005, pp. 1088-1092.
[42] S. Ratnasamy, P. Francis, M. Handley, R. Karp and S. Schenker, "A scalable content-addressable network", in Proceeding of ACM SIGCOMM, pp. 161-172, Aug. 2001.
[43] N. Roy, S. K. Das, K. Basu and M. Kumar, “Enhancing Availability of Grid Computational Services to Ubiquitous Computing Applications,” in Proceeding of 19th IEEE International Parallel and Distributed Processing Symposium, pp.92a-92a, 2005.
[44] C. Santivanez, R. Ramanathan, and I. Stavrakakis, “Making Link-State Routing Scale for Ad Hoc Networks,” Proceedings of the 2nd ACM International. Symposium on Mobile Ad Hoc Net. & Compputing, pp.22-32, 2001.
[45] B. Schneier, Applied Cryptography: Protocols, Algorithms, and Source Code in C, John Whily & Sons, Inc. 1994.
[46] K. Shin and P. Ramanathan, “Diagnosis of Processors with Byzantine Faults in a Distributed Computing Systems,” Proceedings of International Conference on Fault-Tolerant Computing, pp.55-60, 1987.
[47] A. Silberschatz, P.B. Galvin, G. Gagne, Operating System Concepts 6th Ed., John Wiley & Sons, Inc, 2002.
[48] T. Simunic “Power Saving Techniques for Wireless LANs,” Proceedings of Design, Automation and Test in Europe, vol. 3, pp. 96-97 2005.
[49] E. Sit, R. Morris, “Security Considerations for Peer-to-Peer Distributed Hash Tables,” Proceedings for the 1st International Workshop on Peer-to-Peer Systems, pp. 261-269, 2002.
[50] H. S. Siu, Y.H. Chin, 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.
[51] H.S. Siu, Y.H. Chin, and W.P. Yang, “Byzantine Agreement in the Presence of Mixed Faults on Processors and Links”, IEEE Transaction on Parallel and Distributed System, vol. 9, no.4, pp. 335-345, 1998.
[52] H.S. Siu, Y.H. Chin, and W.P. Yang, “Reaching Strong Consensus in the Presence of Mixed Failure Types,” Information Sciences: An International Journal, vol.108, nol.1-4, pp.157-180, 1998.
[53] K.N. Sivarajan and R. Ramaswami, “Lightwave Networks Based on de Bruijn Graphs,” IEEE/ACM Trans. On Networking, vol. 2, no. 1994.
[54] I. Stoica, R. Morris, D. Karger, M. F. Kaashoek, and H. Balakrishnan, "Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications," in Proceeding of ACM SIGCOMM, pp. 149-160, 2001.
[55] Y.F. Tsou, “ A particular Solution for Agreement Problem under Cluster-oriented MANET,” Master Thesis, Department of Information Management, Chaoyang Technology of University, Taiwan, 2007.
[56] J. Turek and D. Shasha, “The Many Faces of Consensus in Distributed Systems,” IEEE Computer, Vol. 25, No. 6, 1992, pp. 8-17.
[57] X. Wang and J. Cao, “An Optimal Early Stopping Uniform Consensus Protocol in Synchronous Distributed Systems with Orderly Crash Failure,” Proceeding of the 23th International Conference on Distributed Computing Systems, pp.76-81, 2003.
[58] S.C. Wang and C.F. Cheng, “Eventually Dual Failure Agreement,” in Fundamenta Informaticae, vol. 57, no. 1, pp.79-99, 2003
[59] S.C. Wang, Y.H. Chin, and K.Q. Yan, “Reaching a Fault Detection Agreement,” Proceedings International Conference on Parallel Processing, pp.251-258, 1990.
[60] S.C. Wang, Y.H. Chin, and K.Q. Yan, “Byzantine Agreement in a Generalized Connected Network,” IEEE Transactions on Parallel and Distributed System, vol.6, no.4, pp.420-427, 1995.
[61] S.C. Wang、K.Q. Yan and C.F. Cheng, “Achieving High Efficient Byzantine Agreement with Dual Components Failure Mode on a Multicasting Network,” Proceedings of the 9th IEEE International Conference on Parallel and Distributed Systems, pp. 577-582, 2002.
[62] S.C. Wang、K.Q. Yan and C.F. Cheng, “Evidence-based MultiCasting Fault Diagnosis Agreement with Fallible Processors”, Proceedings of the 32nd International Conference on Parallel Processing, pp.69-74, 2003.
[63] S.C. Wang, K.Q. Yan and H.C. Hsieh, “The New Territory of Mobile Agreement,” Computer Standards & Interfaces, vol. 26, pp. 435-447, 2004.
[64] S.C. Wang, K.Q. Yan, H.C. Hsieh, “Reaching Consensus Underlying a Mobile Environment,” Proceeding of the 2003 Digital Life and Internet Technology Symposium, 2003.
[65] S.C. Wang, J.E. Yang, K.Q. Yan, and C.F. Cheng, “Achieving High Efficient Consensus in a Hybrid Fallible Multicasting Network,” Proceedings of International Conference on Systems Engineering, 2002.
[66] S.C. Wang, K.Q. Yan and G.Y. Zheng, “Dual Agreement Virtual Subnet Protocol for Mobile Ad-Hoc Networks,” Proceeding of the 22nd Annual ACM Symposium on Applied Computing, pp. 11-15, 2007.
[67] S.C. Wang、W.P. Yang and C.F. Cheng, “Byzantine Agreement on Mobile Ad-Hoc Network,” Proceeding of the IEEE International Conference on Networking, Sensing and Control, pp. 52-57, 2004.
[68] D. B. West, Introduction to Graph Theory, 2nd. Ed., Prentice Hall 2001.
[69] R. Xu and D. Wunsch, “Survey of clustering algorithms,” IEEE Transactions on Neural Networks, vol. 16, no. 3, pp. 645-678, 2005.
[70] K.Q. Yan, Y.H. Chin and S.C. Wang, “Optimal Agreement Protocol in Malicious Faulty Processors and Faulty Links,” IEEE Transactions on Knowledge and Data Engineering, vol.4, no. 3, pp.266-280, 1992.
[71] K.Q. Yan, S.C. Wang, Y.F. Tsou, “Revisit Consensus in a Dual Fallible Clustered-MANET,” Proceeding of the 2006 Taiwan Academic Network Symposium, 2006.
[72] K.Q. Yan, S.C. Wang G.Y. Zheng, “Reaching Dual Fallible Virtual Subnet Consensus,” Proceeding of the 3rd International Conference on Soft Computing and Intelligent Systems and 7th International Symposium on advanced Intelligent Systems, pp.20-24, 2006.