HOME JOURNALS CONTACT

Information Technology Journal

Year: 2003 | Volume: 2 | Issue: 2 | Page No.: 104-115
DOI: 10.3923/itj.2003.104.115
Byzantine Agreement under Unreliable Multicasting Network
S.C. Wang, K.Q. Yan and C.F. Cheng

Abstract: In practice, the communication media in the network are fallible. However, in previous results of the Byzantine Agreement (BA), most of the researches are focus on the fallible component in the network is processor only. This treatment would make an innocent processor would not be able to reach a common agreement due to its faulty communication media. In this paper, we revisit the BA problem in an unreliable MultiCasting Network (MCN) and we also enlarge the fault-tolerant capability by allowing dormant faults and malicious faults to exist in an MCN. The proposed protocols can make each fault-free processor reach a common agreement value by only one round of message exchange and can tolerate the maximum number of faulty communication media.

Fulltext PDF

How to cite this article
S.C. Wang, K.Q. Yan and C.F. Cheng , 2003. Byzantine Agreement under Unreliable Multicasting Network. Information Technology Journal, 2: 104-115.

Keywords: multicasting network, byzatine agreement, parallel processing, dormant fault, malicious fault, dual failure mode and multicasting network

REFERENCES
  • Bar-Noy, A., D. Dlove, C. Dwork and H.R. Strong, 1987. Shifting gears: Changing algorithms on the fly to expedite byzantine agreement. Proceedings of the Symposium on Principles of Distributed Computing, Aug. 10-12, New York, USA., pp: 42-51.

  • Barborak, M., M. Malek and A. Dahubra, 1993. The consensus problem in fault-tolerant computing. ACM Comput. Surveys, 25: 171-220.
    Direct Link    

  • Deo, N., 1974. Graph Theory with Applications to Engineering and Computer Science. Prentice-Hall, Englewood Cliffs, New Jersey, USA

  • Fisher, M.J. and N.A. Lynch, 1982. A lower bound for the assure interactive consistency. Inform. Process. Lett., 14: 183-186.
    Direct Link    

  • Fischer, M., M. Paterson and N. Lynch, 1985. Impossibility of distributed consensus with one faulty process. ACM J., 32: 374-382.
    Direct Link    

  • Halsall, F., 1995. Data Links, Computer Networks and Open Systems. 4th Edn., Addison-Wesley Publishers Ltd., Boston

  • Lamport, L., R. Shostak and M. Pease, 1982. The byzantine generals problem. ACM Trans. Programm Languages Syst., 4: 382-401.
    Direct Link    

  • Meyer, F.J. and D.K. Pradhan, 1991. Consensus with dual failure modes. IEEE Trans. Parallel Distributed Syst., 2: 214-222.
    CrossRef    

  • Pease, M., R. Shostak and L. Lamport, 1980. Reaching agreement in the presence of faults. ACM J., 2: 228-234.
    Direct Link    

  • Silberschatz, A., P.B. Galvin and G. Gagne, 2002. Operating System Concepts. 6th Edn., John Wiley and Sons, New York

  • Siu, H.S., Y.H. Chin and W.P. Yang, 1996. A note on consensus on dual failure modes. IEEE Trans. Parallel Distributed Syst., 7: 225-230.
    Direct Link    

  • Wang, S.C., K.Q. Yan, S.H. Kao and L.Y. Tseng, 2000. Consensus with dual link failure modes on a generalized network. In CY Journal, pp: 35-52.

  • Wang, S.C., Y.H. Chin and K.Q. Yan, 1995. Byzantine agreement in a generalized connected network. IEEE Trans. Parallel Distributed Syst., 6: 420-427.
    Direct Link    

  • Yan, K.Q., Y.H. Chin and S.C. Wang, 1992. Optimal agreement protocol in malicious faulty processors and faulty links. IEEE Trans. Data Knowledge Eng., 4: 266-280.
    Direct Link    

  • Yan, K.Q., S.C. Wang and Y.H. Chin, 1999. Consensus under unreliable transmission. Inform. Process. Lett., 69: 243-248.
    Direct Link    

    • © Science Alert. All Rights Reserved