Agreement under faulty interfaces

Abstract

In this paper we study the problem of achieving Byzantine agreement among a set of processors, where the processors are computationally sound but their interfaces with the communication channels may be faulty. We consider three types of fault, namely message corruption, message loss, and spurious message generation. We present the following results for this model: (i) If all three types of faults are present then the problem is equivalent to the classical Byzantine generals problem. (ii) In the cases where only message corruption can occur, agreement becomes trivial and can be achieved in one round. (iii) If spurious message generation is ruled out, that is, when interfaces may fault only when sensitized, agreement is possible irrespective of the ratio of the number of processors having faulty interfaces with the total number of processors.