AN ALGORITHM FOR IDENTIFICATION OF MALICIOUSLY FAULTY UNITS ?

Franc Novak
Institute Jo?ef Stefan, University of Ljubljana
Jamova 39, 61111 Ljubljana, Slovenia
Sandi Klav?ar
Department of Mathematics, PF Maribor
Koro?ka c. 160, 62000 Maribor, Slovenia

Abstract
The paper proposes an algorithm for identiocation 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 identioed as malicious, sends to the other units, is calculated. It is proved that if a unit can be identioed as malicious by sending some dioeerent messages to the other units, then this can be done in the two consecutive phases. These results form the core of the proposed algorithm.

KEY WORDS: Fault>=tolerance, distributed systems, Byzantine agreement, diagnosis.
C.R. CATEGORIES: F.2.2, nonnumerical algorithms and problems.

?Published in Intern. J. Computer Math., Vol. 48, pp 21-29, 1993.