
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 faultfree 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 2129, 1993.