On the improbability of reaching Byzantine agreements

Abstract

It is well known that for the Byzantine Generals Problem, no deterministic protocol can exist for an n-processor system if the number t of faulty processors is allowed to be as large as n/3. In this paper we investigate the maximum achievable agreement probability Βn,t in a model in which the faulty processors can be as devious and powerful as possible. We also discuss a restricted model with Βn,t denoting the corresponding maximum achievable probability. We will prove that: (i) for n = 3, t = 1 (the first nontrivial case), Β3,1 = (√5 - 1)/2 (the reciprocal of the golden ratio); (ii) for all ε with 0 < ε < 1, if t/n > 1 - log (1 -ε)1/2/ log (1 - (1 -ε)1/2) then Βtn,t < ε