An algorithm for identification of maliciously faulty units

Abstract

The paper proposes an algorithm for identification of malicious units in a fully connected system. The assumed scenario is the same as in an execution of a full information gathering algorithm for Byzantine agreement without authentication. A criterion that can be used by a fault-free unit to identify a malicious unit is described. The exact bound of the maximum number of equal values that a unit which can be identified as malicious, sends to the other units, is calculated. It is proved that if a unit can be identified as malicious by sending some different messages to the other units, then this can be done in the two consecutive phases. These results form the core of the proposed algorithm.

Keywords:

• Fault-tolerance
• distributed systems
• Byzantine agreement
• diagnosis

C.R. CATEGORIES::

• F.2.2
• nonnumerical algorithms and problems.

^*Supported in part by the Research Council of Slovenia

^*Supported in part by the Research Council of Slovenia

^*Supported in part by the Research Council of Slovenia

^*Supported in part by the Research Council of Slovenia

Notes

^*Supported in part by the Research Council of Slovenia

^*Supported in part by the Research Council of Slovenia