PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
Tytuł artykułu

Byzantine Agreement & Fault Diagnosis Agreement in Dynamic Ad-Hoc Environment

Wybrane pełne teksty z tego czasopisma
Identyfikatory
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
Since wireless communication and mobile computing are becomingmore and more ubiquitous, the reliability and fault tolerance of the Mobile Ad-hoc Network (MANET) has become an important topic. In order to provide a reliable environment, a mechanism that allows a set of nodes to reach a common agreement, even in the presence of faulty nodes, is needed. Therefore, the Byzantine Agreement (BA) problem has drawn attention of more researchers. Traditionally, the BA problem was focused on wired networks. We know that the physical topology of a wired network is static, but the physical topology of an MANET is dynamic. Thus, previous BA protocols are not applicable in an MANET. In this paper, a new protocol is proposed to solve the BA problem with malicious faulty components in dynamic MANET. Furthermore, we also propose a new Fault Diagnosis Agreement (FDA) protocol to detect/locate faulty components to provide a highly reliable environment. From the performance perspective, the proposed protocols use the minimum number of message exchanges and can tolerate/detect/locate the maximum number of faulty nodes allowed in the dynamic network.
Wydawca
Rocznik
Strony
161--187
Opis fizyczny
bibliogr. 31 poz., tab., wykr.
Twórcy
autor
autor
autor
  • Department of Information Management, Chaoyang University of Technology, 168, GiFeng E. Rd., WuFeng, TaiChung, Taiwan 413, ROC, scwang@cyut.edu.tw
Bibliografia
  • [1] C. E. Perkins and E. M. Royer: Ad-Hoc On-Demand Distance Vector Routing, Proc. of the 1st IEEE Workshop on Mobile Computing Systems and Applications, pp.90-100, 1999.
  • [2] C.E. Perkins: Ad Hoc Networking, Addison-Wesley, 2001
  • [3] X. Hong, K. Xu, andM. Gerla: Scalable routing Protocols forMobile Ad Hoc Networks, IEEE Network, vol. 16, no.4, pp.11-21, 2002.
  • [4] G. Pei, M. Gerla, and T.W. Chen: Fisheye State Routing: A Routing Scheme for Ad Hoc Wireless Network, Proc. of the IEEE Int'l Conf. on Communications, pp.70-74, 2000.
  • [5] C. Santivanez, R. Ramanathan, and I. Stavrakakis: Making Link-State Routing Scale for Ad Hoc Networks, Proc. of the 2nd ACM Int'l. Symposium on Mobile Ad Hoc Net. and Compputing, pp.22-32, 2001.
  • [6] P. Jacquet, P. Muhlethaler, T. Clausen, A. Laouiti, A. Qayyum and L. Viennot: Optimized Link State Routing Protocol for Ad Hoc Networks, Proc. of IEEE Int'l. Technology for the 21st Century, 2000.
  • [7] B. Bellur and R. G. Ogier: A Reliable, Efficient Topology Broadcast Protocol for Dynamic Networks. Proc. of the 18th IEEE INFOCOM, pp.178-186, 1999.
  • [8] D. B. Johnson and D. A. Maltz: Dynamic Source Routing in Ad Hoc Wireless Networks, Mobile Computing, Kluwer, 1996.
  • [9] 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.
  • [10] A. Silberschatz, P.B. Galvin, G. Gagne: Operating System Concepts 6th Ed., John Wiley & Sons, Inc, 2002.
  • [11] 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.
  • [12] L. Lamport, R. Shostak, andM. Pease: The Byzantine Generals Problem, ACMTrans. on Programming Languages and Systems, vol.4, no.3, pp.382-401, 1982.
  • [13] A. Bar-Noy, D. Dolev, C. Dwork and H. R. Strong: Shifting Gears: Changing Algorithms on the Fly to Expedite Byzantine Agreement, Inf. Comput., vol.97, no.2, pp.205-233, 1992.
  • [14] 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.
  • [15] T. Araragi: Byzantine Fault Tolerance for Agent Systems: Proc. of the International Conf. on Dependability of Computer Systems, pp.232-239, 2006.
  • [16] M. Fisher, and N. Lynch: A Lower Bound for the Assure Interactive Consistency, Information Processing Letters, vol.14, no.3, pp.183-186, 1982.
  • [17] M. Okum: Agreement among Unacquainted Byzantine Generals, Lecture Note in Computer Sciences, vol.3724, pp.499-500, 2005.
  • [18] H. S. Siu, Y.H. Chin,W.P. Yang: A Note on Consensus on Dual FailureModes, IEEE Trans. on Parallel and Distributed Systems, vol.7, no.3, pp.225-229, 1996.
  • [19] X. Wang and J. Cao: An Optimal Early Stopping Uniform Consensus Protocol in Synchronous Distributed Systems with Oderly Crash Failure, Proc. of the 23th Int'l Conference on Distributed Computing Systems, pp.76-81, 2003.
  • [20] S.C. Wang, Y.H. Chin, and K.Q. Yan: Reaching a Fault Detection Agreement, Proc. Int'l Conf. Parallel Processing, pp.251-258, 1990.
  • [21] S.C.Wang, Y.H. Chin, and K.Q. Yan: Byzantine Agreement in a Generalized Connected Network, IEEE Trans. on Parallel and Distributed System, vol.6, no.4, pp.420-427, 1995.
  • [22] S.C. Wang and C.F. Cheng: Eventually Dual Failure Agreement, in Fundamenta Informaticae, vol. 57, no. 1, pp.79-99, 2003
  • [23] S.C.WangBK.Q. Yan and C.F. Cheng: Achieving High Efficient Byzantine Agreement with Dual Components Failure Mode on a Multicasting Network, Proc. of the 9th IEEE Inte'l Conference on Parallel and Distributed Systems, pp. 577-582, 2002.
  • [24] S.C. WangBK.Q. Yan and C.F. Cheng: Evidence-based MultiCasting Fault Diagnosis Agreement with Fallible Processors, Proc. of the 32nd Inte'l Conference on Parallel Processing, pp.69-74, 2003.
  • [25] K.Q. Yan, Y.H. Chin and S.C. Wang: Optimal Agreement Protocol in Malicious Faulty Processors and Faulty Links. IEEE Trans. on Knowledge and Data Engineering, vol.4, no. 3, pp.266-280, 1992.
  • [26] H.S. Hsiao, Y.H. Chin, W.P. Yang: Reaching Fault Diagnosis Agreement under a Hybrid Fault Model, IEEE Trans. on Computers, vol. 49, no. 9, pp.980-986, 2000.
  • [27] F. Preparata, G.Metze, and R. Chien: On the Connection Assignment Problem of Diagnosable Systems, IEEE Trans. on Electronic Computing, vol.16, pp.848-858, 1967.
  • [28] K.V.S. Ramarao and J.C. Adams: On the Diagnosis of Byzantine Faults, Proc.of Inte'l Conference on Reliable Distributed Systems, pp.144-153, 1988.
  • [29] K. Shin and P. Ramanathan: Diagnosis of Processors with Byzantine Faults in a Distributed Computing Systems, Proc. of Inte'l Conference on Fault-Tolerant Computing, pp.55-60, 1987.
  • [30] N.Malpani, J. L.Welch and N. Vaidya: Leader election algorithms for mobile ad hoc networks, Proc. of the 4th Inte'l workshop on Discrete algorithms and methods for mobile computing and communications, pp.96-103, 2000.
  • [31] D. R. Broug: Logic Programming. New Frontiers, Kluwer Academic, 1992.
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-article-BUS8-0003-0057
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.