Correction to Byzantine Agreement in Expected Polynomial Time, JACM 2016
Valerie King Jared Saia













Correction to “Byzantine Agreement in Expected Polynomial Time"
    Valerie King val@cs.uvic.ca; Department of Computer Science, University of Victoria, P.O.
Box 3055, Victoria, BC, Canada V8W 3P6. Jared Saia saia@cs.unm.edu; Department of Computer Science, University of New Mexico, Albuquerque, NM 87131-1386.
    
=======================================================================================================================================================================================================================================================





	This is a correction to the paper “Byzantine Agreement in Expected
Polynomial Time" which appeared in the Journal of the ACM in 2016. It corrects a failure in the paper to consider the adversary's ability to decide the number of fair coinflips in an iteration, where this number ranges between n(n-t) and n(n-2t). 
 









§ INTRODUCTION



In <cit.>, King and Saia describe an algorithm to solve Byzantine agreement in expected polynomial time. Their general strategy is to run an algorithm based on work of Ben-Or <cit.> (cf. Bracha <cit.>) that depends on simulating a global coin.  In every iteration of the Ben-or type algorithm, there is a direction that is good in the sense that if the simulated global coin lands in that direction, the processors come to agreement and terminate.

 King and Saia simulate a global coin via summing coinflips from all processors, and measuring the deviation from zero of this sum.  They show that in each iteration, with constant probability there is large “good" deviation by the good coinflips in the good direction.  When this occurs, if there is no agreement,  then there must be “bad" deviation caused by the adversarially-controlled (bad) processors which counterbalances the good deviation. Eventually, the deviation by bad processors becomes unusually frequent and detectable, so that good processor will eventually exclude these from their calculations in future global coin simulations. 

 
 


In each iteration of the Ben-Or type algorithm, each good processor generates a stream of up to n fair coinflips.  
In Section 4.1, Property 2 of x-sync ensures that at most t of the coinflip streams generated by good processors  contain fewer than n coinflips.  It was recently observed by Melnyk, Wang and Wattenhoffer <cit.> that the analysis in <cit.> failed to take into account the effect that an adversarial stopping strategy on these t streams may have on the value of the sum of coinflips generated by good processors.

In this brief announcement, we correct this issue.  First, we show (Fact 3 below) that we can bound the maximum value obtained during a stream of tn coins, and pessimistically use this maximum in lieu of the final sum of tn coins.  Next,  we describe additional slight changes required in the analysis of the remainder of the paper to account for this new bound.  This includes decreasing the constant factor in the resilience for the polynomial time algorithm, Variant 1.











§ CORRECTIONS IN SECTION 5


First, insert the following result <cit.>, as Fact 3 in Section 5.1. 


Fact 3: Let M_n be the maximum value of a symmetric, 1-dimensional random walk after n steps and let S_n be the value of the random walk at step n.  For a symmetric random walk, for any r ≥ 1, Pr(M_n ≥ r)= Pr(S_n = r) + 2 Pr(S_n > r), which implies     
Pr(M_n ≥  r) < 2 Pr(S_n ≥ r). 

The JACM paper identifies two sources of bad deviation other than that caused by coinflips from bad processors:  (1) coinflips from ≤ t  good processors which have been excluded because they are thought to be bad which sum to ≤β/2; and (2) t deviation caused by a total of t “ambiguous"  coins (from the asynchrony).  In this writeup, we add (3), the effect of the adversary possibly stopping up to t of the good coinflip streams.



 §.§ Our Corrections

 We change β/2 to β/4 for each of the coinflips of type (1)  and type (3) and modify Lemma 5.2 to account for these effects. 


Lemma 5.2.  (1)  A stream of between 1 and nt coin flips which can be stopped adversarially anywhere in this range has deviation exceeding β/4 = √(2n(n-t))/4 -t/2 with probability at most (1/2) e^-(β/4)^2/2nt. If t < .005n, then this probability is at most e^-11.

(2) A stream of between n(n-2t) and n(n-t) coin flips which can be stopped adversarially anywhere in this range has deviation of at least α'=√(2n(n-2t)) -β/4 in any specified direction with probability exceeding 1/20. 


(1) Consider a random walk of nt steps, starting at the origin, where each step is equally likely to be 1 or -1. By Fact 3, the probability that its maximum value is at least β/4 is no more than twice the probability that the sum of nt coin flips is at least β/4, which is at most 2 e^-(β/4 )^2/2tn (by Lemma 5.2 old). If t< .005n, then this probability is at most e^-11. 

(2) The stream consists of the first n(n-2t) good coins plus a stream which the adversary can stop at any point afterwords. By Lemma 5.1, the first part of the stream has deviation α with  probability greater than .211. The second part of the stream can, in the worst case, be adjusted by the adversary to the maximum deviation achieved which equals or exceeds β/4 (in the opposite direction) with probability at most e^-11. The probability that the entire stream has deviation at least α' is at least the probability that the first event occurs and the second doesn't. 
Hence the probability that the entire stream has deviation α' is at least .211-e^-11>1/20.


Additional corrections in Section 5 are as follows.

 
  * In Lemma 5.3: (1)  Replace α by α'; and (2) Replace β/2 by β/4.
 
  * In proof of Lemma 5.3: Change “From Lemma 5.1" to  “From Lemma 5.2(2)"

  * In Lemma 5.4: (1) Change α to α'; and (2) Change β/2 to β/4

  * In proof of Lemma 5.4, line 7 page 14: Change β/2 to β/4

  * In Lemma 5.5: Change t< n/36 to t< 1/72.




§ CORRECTIONS FOR VARIANT 1

For Variant 1: 
Let H be the matrix filled by a stream of independent, random -1,1 coinflips except in up to t adversarially chosen columns.  In these columns, the adversary picks points to stop the stream  as it is filling a column, and the rest of the column (the suffix) is filled with 0's. 

Then H =  H' + W where H' is a matrix of -1,1 independent, random coin flips, and W is all 0's except the suffixes in columns changed by the adversary, where its entries are the negation of the columns of H'.

Now change the definition of G, in Section 6, second paragraph after Theorem 6.1 as follows.  “All entries of G in columns controlled by bad processors are set to 0.  For j corresponding to a good processor, the (i,j) entry of G is the sum of the j-th column for the matrix H generated in iteration i of Algorithm 5."

Then insert the following two paragraphs immediately before Corollary 6.2.  “Note that G=R+Z, where R is a matrix where every entry in each good column is set to the sum of n fair coinflips, and every entry in each bad column is set to 0.  Additionally, Z is a matrix where the (i,j) entry is the sum of the j-th column of the matrix W generated in iteration i of Algorithm 5."

“By a property of matrix norms, |G| ≤ |R| +|Z|.
Hence,  Pr(|G| >a)  ≤  Pr (|R|+|Z| >a) ≤ Pr(|(R|>a/2) + Pr(|Z|>a/2), where the last step holds by a union bound. 
Pr(|R|>a/2) is bounded by Theorem 6.1.  Pr (|Z| > a/2) is bounded by Theorem 6.1 as  well. Note that Z is a matrix of independent random variables  some of which are set to 0 and some of which are distributed as the sum of a number of coinflips  between 1 and n.  The number is set adversarially but this does not affect the analysis. 

Next, change the statement of Corollary 6.2 to refer to both the matrices Z and R, instead of G, and insert the following statement after Corollary 6.2:  
“Applying Corollary 6.2 to both Z and R,
we have Pr(|G| > (6+ 2ϵ)√(n(m+n))) < 2(m+n)^-1." 

In Lemmas 6.3, 6.4, 6.5, 6.6, 6.7, and their proofs, replace the expression 3+ϵ with 6+2ϵ, and the expression 4+ϵ with 7+2ϵ. 
In proof of Lemma 6.7, replace 1/(m+n) by 2/(m+n) each time it appears. 
In statement of Lemma 6.7 and Theorem 1.1, replace t < 4.25*10^-7 n by t<3.3 * 10^-8n. 

In the paragraph before Lemma 6.4, replace  "When t< n/36, β/2 > 23n/36"  with "When t< 10^-6n, (β/2)^2 > .49999n^2" and 
replace the sentence “Then this inequality holds..." with  “Then this inequality holds when t < c_1n(.183^2)β^2/6(7+2ϵ)^2n^2, which requires t < (2/3) (.001) (.0183)^2 (.49999)^2 (7+2 ϵ)^-2 n ≤ 1.14 * 10^-9n.
  



§ CORRECTIONS FOR VARIANT 2

For Variant 2, 
we need to change Lemma 7.1 as follows.
  Bottom of page 18: Omit “Further, note...Throughout the proof".  Insert “The maximum sum of the coinflips of t possibly incomplete streams of up to a total of c_1 m n t coins is no greater than the maximum value of a random walk reached during this many steps. Hence, by Lemma 5.2,  the probability that X ≥ (β/6)c_1m is no greater than 2 Pr(Y≥ (β/6)c_1m), where Y is the summation of ntc_1m random coinflips." 

Make the following changes to the proof of Lemma 7.1:

Substitute Y for X in the third paragraph of Lemma 7.1 and the first line of the first set of equations. In the second set of equations, add a factor of 2 in front of the right side of each equation except the last.

abbrv



