Revisiting fault diagnosis agreement in a new territory

ABSTRACT

In convention, to consensus has been discussed variously. The way of fault masking is commonly used to reach consensus. However, reaching consensus is not enough in a high reliability application. Therefore, in this study, the fault diagnosis agreement is visited. The proposed protocol does not only reach an agreement for healthy processors but also detect and locate the faulty components in a synchronous unreliable network. We also enlarge the fault tolerance capability by allowing both dormant faults and malicious faults exist in a network. That is, the proposed protocol can tolerate, detect and locate the maximum number of faulty components with the dual failure mode to solve the consensus problem and fault diagnosis agreement problem in a synchronous distributed environment by minimum number of rounds of message exchange.

REFERENCES

• 1: Amotz Bar-Noy , Danny Dolev , Cynthia Dwork , H. Raymond Strong, Shifting gears: changing algorithms on the fly to expedite Byzantine agreement, Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, p.42-51, August 10-12, 1987, Vancouver, British Columbia, Canada [doi>10.1145/41840.41844]
• 2: Michael Barborak , Anton Dahbura , Minoslaw Malek, The consensus problem in fault-tolerant computing, ACM Computing Surveys (CSUR), v.25 n.2, p.171-220, June 1993 [doi>10.1145/152610.152612]
• 3: Pallab Dasgupta, Agreement under faulty interfaces, Information Processing Letters, v.65 n.3, p.125-129, Feb. 1998 [doi>10.1016/S0020-0190(97)00202-0]
• 4: D. Dolev (1982). The Byzantine Generals Strike Again. Journal of Algorithms, 3(1), 14--30.
• 5: Skeen, D., and Stonebraker, M (1983). A Formal Model of Crash Recovery in a Distributed System. IEEE Trans. Software Engineering, 9(4), 219--228.
• 6: Danny Dolev , Rüdiger Reischuk, Bounds on information exchange for Byzantine agreement, Journal of the ACM (JACM), v.32 n.1, p.191-204, Jan. 1985 [doi>10.1145/2455.214112]
• 7: Michael J. Fischer, The Consensus Problem in Unreliable Distributed Systems (A Brief Survey), Proceedings of the 1983 International FCT-Conference on Fundamentals of Computation Theory, p.127-140, August 21-27, 1983
• 8: D. K. Gifford (1979). Weighted Voting for Replicated Data. Technical Report. CSL-79-14, XEROX Palo Alto Research Center.
• 9: Fred Halsall, Data communications, computer networks and open systems (4th ed.), Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1995
• 10: Leslie Lamport , Robert Shostak , Marshall Pease, The Byzantine Generals Problem, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.3, p.382-401, July 1982 [doi>10.1145/357172.357176]
• 11: F. J. Meyer , D. K. Pradhan, Consensus With Dual Failure Modes, IEEE Transactions on Parallel and Distributed Systems, v.2 n.2, p.214-222, April 1991 [doi>10.1109/71.89066]
• 12: F. Preparata, G. Metze, and R. Chien (1967). On the Connection Assignment Problem of Diagnosable Systems. IEEE Trans. on Electronic Computing, 16, 848--858.
• 13: M. Pease , R. Shostak , L. Lamport, Reaching Agreement in the Presence of Faults, Journal of the ACM (JACM), v.27 n.2, p.228-234, April 1980 [doi>10.1145/322186.322188]
• 14: K. V. S. Ramarao and J. C. Adams (1988). On the Diagnosis of Byzantine Faults. In Proc. of Reliable Distributed Systems. pp. 144--153.
• 15: Hin-Sing Siu , Yeh-Hao Chin , Wei-Pang Yang, A Note on Consensus on Dual Failure Modes, IEEE Transactions on Parallel and Distributed Systems, v.7 n.3, p.225-230, March 1996 [doi>10.1109/71.491575]
• 16: Hin-Sing Siu , Yeh-Hao Chin , W.-P. Yang, Byzantine Agreement in the Presence of Mixed Faults on Processors and Links, IEEE Transactions on Parallel and Distributed Systems, v.9 n.4, p.335-345, April 1998 [doi>10.1109/71.667895]
• 17: K. Shin and P. Ramanathan (1987). Diagnosis of Processors with Byzantine Faults in a Distributed Computing System. In the Proc. of Fault-Tolerant Computing, pp. 55--60.
• 18: J. H. Wesley, et al, (1978). SIFT: Design and Analysis of a Fault-Tolerant Computer for Aircraft Control. In the Proc. of IEEE 66(10), pp. 1240--1255.
• 19: S. C. Wang, Y. H. Chin, and K. Q. Yan (1990). Reaching a Fault Detection Agreement. In the Proc. of Int'l Conference Parallel Processing, pp. 251--258.
• 20: S. C. Wang , Y. H. Chin , K. Q. Yan, Byzantine Agreement in a Generalized Connected Network, IEEE Transactions on Parallel and Distributed Systems, v.6 n.4, p.420-427, April 1995 [doi>10.1109/71.372796]
• 21: S. C. Wang , K. Q. Yan, Reaching Fault Diagnosis Agreement on Dual Link Failure Mode, Proceedings of the Seventh International Conference on Parallel and Distributed Systems (ICPADS'00), p.291, July 04-07, 2000
• 22: S. C. Wang, K. Q. Yan, S. H. Kao and L. Y. Tseng (2000). Consensus with Dual Link Failure Modes on a Generalized Network. CY Journal, 35--52.
• 23: K. Q. Yan and Y. H. Chin (1988). An Optimal Solution for Consensus Problem in an Unreliable Communication System. In the Proc. of the Int'l Conf. Parallel Processing, pp. 388--391.
• 24: K. Q. Yan , S. C. Wang , Y. H. Chin, Consensus under unreliable transmission, Information Processing Letters, v.69 n.5, p.243-248, March 12, 1999 [doi>10.1016/S0020-0190(99)00015-0]

INDEX TERMS

Keywords:
consensus, distributed system, fault diagnosis, fault tolerance