EFFICIENT AGREEMENT USING FAULT-DIAGNOSIS

We give an extremely simple Byzantine agreement protocol that uses 0(t 2) processors, min (f + 2, t + 1) rounds of communication, 0 (n . t - f - log Absolute value of V) total message bits, and 0 (log Absolute v alue of V) maximum message size, where n is the total number of proces sors that actually participate in the protocol, t is an upper bound on the number of faulty processors, f is the number of processors that a ctually fail in a given execution, and V is the set of possible inputs . This protocol uses roughly the same resources as a more complex prot ocol due to Dolev, Reischuk, and Strong. By adding explicit fault diag nosis to our first protocol, we produce a somewhat more complicated pr otocol that uses 0 (t1.5) processors, min (f + 2, t + 1) rounds, 0 (n - t2 . f . log Absolute value of V) total message bits, and 0 (t - log Absolute value of V) maximum message size.