on the improbability of reaching byzantine agreements
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 &Bgr; 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 &Bgr; n,t denoting the corresponding maximum achievable probability. We will prove that: (i) for n = 3, t = 1 (the first nontrivial case), &Bgr; 3,1 = (?5 - 1)/2 (the reciprocal of the golden ratio); (ii) for all &egr; with 0   1 - log (1 -&egr;) 1/2 / log (1 - (1 -&egr;) 1/2 ) then &Bgr; t n,t < &egr;
processor systems paper probability model case log