Almost everywhere to everywhere Sample Clauses

Almost everywhere to everywhere asynchronous). Let n be the number of processors in a fully asynchronous full information message passing model with a nonadaptive adversary. Assume that (1/2+ γ)n good pro- cessors agree on a string of length O(log n) which has a constant fraction of ran- dom bits, and where the remaining bits are fixed by a malicious adversary after seeing the random bits. Then for any positive constant γ, there exists a protocol which w.h.p. brings all good processors to agreement on n good quorums; runs in polylogarithmic time; and uses O˜(√n) bits of communication per processor. Furthermore, if we assume that same set of good processors have agreed on an input bit (to the Byzantine agreement problem) then this same protocol can bring all good processors to agreement on that bit. A scalable implementation of the protocol in [10] following the lines of [14] would create the conditions in the assumptions of this theorem with probability − − 1 O(1/ log n) in polylogarithmic time and bits per processor with an adversary that controls less than 1/3 fraction of processors. Then this theorem would yield an algorithm to solve asynchronous Byzantine agreement with probability 1 − O(1/ log n). The protocol is introduced in Section 4 of this paper. 2 Combinatorial Lemmas Before presenting our protocol, we discuss here the properties of some combina- torial objects we shall use in our protocol. → { } Let [r] denote the set of integers 1,. .. , r , and [s]d the multisets of size d consisting of elements of [s]. Let H : [r] [s]d be a function assigning multisets of size d to integers. We define the intersection of a multiset A and a set B to be the number of elements of A which are in B. H is a (θ, δ) sampler if at most a δ fraction of all inputs x have |H(x)∩S| > |S| + θ. d s Let r = nc+1. Let i ∈ [nc] and j ∈ [n]. Then we define H(i, j) to be H(in + j) and H(i,∗) to be the collection of subsets H(i + 1),H(i + 2), ..., H(i + n). Lemma 1 ([[9], Lemma 4.7], [[18], Proposition 2.20]). For every s, θ, δ > 0 and r ≥ s/δ, there is a (θ, δ) sampler H : [r] → [s]d with d = O(log(1/δ)/θ2). A corollary of the proof of this lemma shows that if one increases the constant in the expression of d by a factor of c, we get the following: Corollary 1 Let H[r] be constructed by randomly selecting with replacement d elements of [s]. For every s, θ, δ, c > 0 and r ≥ s/δ, for d = O(log(1/δ)/θ2), H(r) is a (θ, δ) sampler H : [r] → [s]d with probability 1 − 1/nc. ∈ → Lemma 2. Let r = nc+1 and s = n. Let H...