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. 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 s 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. 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| + θ. 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 : [r] [s]d be constructed by randomly selecting with replacement d elements of [s]. Call an element y [s] overloaded by H if its inverse image under H contains more than a.d elements, for some fixed element a ≥ 6. The probability that an...