Submit Manuscript

Information Technology Journal

Year: 2003 | Volume: 2 | Issue: 2 | Page No.: 104-115
Facebook Twitter Digg Reddit Linkedin StumbleUpon E-mail
Research Article

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.
PDF References Citation

REFERENCES

  1. 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.
    CrossRef
  2. Barborak, M., M. Malek and A. Dahubra, 1993. The consensus problem in fault-tolerant computing. ACM Comput. Surveys, 25: 171-220.
    Direct Link
  3. Deo, N., 1974. Graph Theory with Applications to Engineering and Computer Science. Prentice-Hall, Englewood Cliffs, New Jersey, USA.
  4. Fisher, M.J. and N.A. Lynch, 1982. A lower bound for the assure interactive consistency. Inform. Process. Lett., 14: 183-186.
    Direct Link
  5. Fischer, M., M. Paterson and N. Lynch, 1985. Impossibility of distributed consensus with one faulty process. ACM J., 32: 374-382.
    Direct Link
  6. Halsall, F., 1995. Data Links, Computer Networks and Open Systems. 4th Edn., Addison-Wesley Publishers Ltd., Boston.
  7. Lamport, L., R. Shostak and M. Pease, 1982. The byzantine generals problem. ACM Trans. Programm Languages Syst., 4: 382-401.
    Direct Link
  8. Meyer, F.J. and D.K. Pradhan, 1991. Consensus with dual failure modes. IEEE Trans. Parallel Distributed Syst., 2: 214-222.
    CrossRef
  9. Pease, M., R. Shostak and L. Lamport, 1980. Reaching agreement in the presence of faults. ACM J., 2: 228-234.
    Direct Link
  10. Silberschatz, A., P.B. Galvin and G. Gagne, 2002. Operating System Concepts. 6th Edn., John Wiley and Sons, New York.
  11. 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
  12. 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.
  13. 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
  14. 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
  15. Yan, K.Q., S.C. Wang and Y.H. Chin, 1999. Consensus under unreliable transmission. Inform. Process. Lett., 69: 243-248.
    Direct Link

Related Articles

Leave a Comment

Your email address will not be published. Required fields are marked *