Eventually Dual Failure Agreement

• Autorzy: Wang S.-C. , Cheng C.-F.
• Języki publikacji: EN

Abstrakty

EN

The Byzantine Agreement (BA) problem is a fundamental problem to consider in designing a fault-tolerance distributed system. Most BA protocols require all the fault-free processors to reach a common agreement at the same round, called an Immediate Byzantine Agreement (IBA), whereas another type of BA protocol allows the fault-free processors to reach a common agreement, called an Eventual Byzantine Agreement (EBA), at different rounds when they receive enough information. Up to now, all the existing EBA protocols are designed to solve the EBA problem based on the single failure type assumption (dormant fault only or malicious fault only) as to fallible processors over a reliable fully connected network. However, in practice, most network topologies would not be fully connected, and the underlying network would not be reliable, which means both dormant and malicious faults may occur within the same network simultaneously. In this study, we shall propose a new protocol to solve the EBA problem with dual failure mode on both processors and communication media (both dormant and malicious faults can happen simultaneously to either the processors or the communication media or both) over an unreliable un-fully connected network. The proposed protocol is the optimal when the above assumptions are considered.

Słowa kluczowe

EN

Immediate Byzantine Agreement; Eventtual Byzantine Agreement; distributed computing; parallel processing

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2003
• Tom: Vol. 57, nr 1
• Strony: 79--99
• Opis fizyczny: Bibliogr. 24 poz.

Twórcy

autor

Wang S.-C.

• Department of Information Management , Chaoyang University of Technology, 168 Gifeng E. Rd., Wufeng, Taichung County, Taiwan 413, R.O.C.

autor

Cheng C.-F.

• Department of Computer & Information Science, National Chiao Tung University, 1001, Ta Hsueh Road, Hsinchu, Taiwan 300, R.O.C.

Bibliografia

• [1] Bar-Noy, A. et al.: Shifting Gears: Changing Algorithms on the Fly To Expedite Byzantine Agreement, Proc. Symposium on Principles of Distributed Computing, 1987.
• [2] Barborak, M., Malek, M., and Dahubra, A.: The Consensus Problem in Fault-Tolerant Computing, ACM Computing Surveys, 25(2), 1993, 171-220.
• [3] Berman, P., Garay, J.A., and Perry, K.J.: Optimal Early Stopping in Distributed Consensus, Proc. 6th International Workshop on Distributed Algorithms, 1992.
• [4] Dasgupta, P.: Agreement under Faulty Interfaces, Information Processing Letters, 65, 1998, 125-129.
• [5] Deo, N.: Graph Theory with Applications to Engineering and Computer Science, Englewood Cliffs, N. J., Prentice-Hall, 1974.
• [6] Dolev, D.: The Byzantine Generals Strike Again, Journal of Algorithms, 3(1), 1982, 14-30.
• [7] Dolev, D., and Reischuk, R.: Bounds on Information Exchange for Byzantine Agreement, Journal of ACM, 32(1), 1985, 191-204.
• [8] Dolev, D., Reischuk, R., and Strong, A.R.: Early Stopping in Byzantine Agreement, ACM for Computing Machinery, 37(4), 1990, 720-741.
• [9] Fischer, M., and Lynch, N.: A Lower Bound for the Assure Interactive Consistency, Information Processing Letters, 14(4), 1982, 183-186.
• [10] Gifford, D. K.: Weighted Voting for Replicated Data, Technical Report. CSL-79-14, XEROX Palo Alto Research Center, September 1979.
• [11] Hadzilacos, V.: Byzantine Agreement under Restricted Types of Failures (not Telling the Truth is Different from Telling Lies), Technical Report 19-83, Aiken Computation Laboratory, Harvard University, Cambridge, Massachusetts, June 1983.
• [12] Halsall, F.: Data Links, Computer Networks and Open Systems, 4th. Ed., Addison-Wesley Publishers Ltd., 1995, 112-125.
• [13] Krings, A. W., and Feyer, T.: The Byzantine Agreement Problem: Optimal Early Stopping, Proc. 32nd Hawaii International Conference on System Sciences (A. Tarlecki, Ed.), LNCS 520, Springer-Verlag, Berlin, 1990.
• [14] Lamport, L., and Fisher, M.: Byzantine Generals and Transaction Commit Protocols, Proc. Opus 62, SRI international (A. Tarlecki, Ed.), LNCS 520, Springer-Verlag, Berlin, 1982.
• [15] Lamport, L., Shostak, R., and Pease, M.: The Byzantine Generals Problem, ACM Transaction on Programming Language Systems, 4(3), 1982, 382-401.
• [16] Meyer, F.J., and Pradhan, D.K.: Consensus with Dual Failure Modes, IEEE Transaction on Parallel and Distributed Systems, 2(2), 1991, 214-222.
• [17] Pease, M., Shostak, R., and Lamport, L.: Reaching Agreement in the Presence of Faults, Journal of ACM, 27(2), 1980, 228-234.
• [18] Perry, K. J.: Early Stopping Protocols for Fault-Tolerant Distributed Agreement, Ph.D. Thesis, Cornell University, January 1985.
• [19] Silberschatz, A.: Galvin, P.B., Gagne, G..: Operating System Concepts, 6th. Ed., John Wiley & Sons, Inc., 2002.
• [20] Siu, H.S., Chin, Y.H. and Yang, W.P.: Byzantine Agreement in the Presence of Mixed Faults on Processors and Links, IEEE Transaction on Parallel and Distributed Systems, 9(4), 1998, 980-986.
• [21] Toueg, Sam, Perry, K. J., and Srikanth, T. K.: Fast Distributed Agreement, SIAM Journal on Computing, 16(3), 1987, 445-457.
• [22] Wang, S.C., Chin, Y.H., and Yan, K.Q.: Byzantine Agreement in a Generalized Connected Network, IEEE Transaction on Parallel and Distributed Systems, 6(4), 1995, 420-427.
• [23] Yan, K.Q., Chin, Y.H., and Wang, S.C.: Optimal Agreement Protocol in Malicious Faulty Processors and Faulty Links, IEEE Transaction on Knowledge and Data Engineering, 4(3), 1992, 266-280.
• [24] Yan, K.Q., Wang, S.C., and Chin, Y.H.: Consensus Under Unreliable Transmission, Information Processing Letters, 69, 1999, 243-248.