The bounds of faulty components on consensus with dual failure modes

ABSTRACT

The consensus is an important topic in the reliable distributed system because the system can cope with the influences from faulty components when the agreement is achieved. Siu, Chin and Yang have indicated that the bound on the number of allowable faulty processors in Meyer and Pradhan's scheme is an overestimated one, and they have given a new fixed bound to the allowable faulty processors. However, we find out that the new bound for the allowable faulty processors by Siu et al. still seems to give the scheme too much credit. In this study, we shall give a more accurate estimation to the bound of the allowable faulty processors.

REFERENCES

• 1: 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]
• 2: 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]
• 3: 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]
• 4: 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]
• 5: 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]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.0 GENERAL
      Subjects: Modeling of computer architecture

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Reliability, availability, and serviceability

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.5 Reliability
          Subjects: Fault-tolerance
      D.4.7 Organization and Design
          Subjects: Distributed systems
      D.4.8 Performance
          Subjects: Modeling and prediction

General Terms:
Performance

Keywords:
consensus, distributed system, dual failure mode, fault tolerance, interconnection networks