Exponential information Clause Samples

Exponential information gathering using f + 1 rounds in a synchronous Byzantine system with at most f faulty processes satisfies validity and agreement, provided n ≥ 3f + 1. Proof. Validity: Immediate application of Lemmas 10.2.1 and 10.2.2 when w = . We have valÕ(j, i) = val(j, i) = val( , j) for all non-faulty j and i, which means that a majority of the valÕ(j, i) values equal the common input and thus so does valÕ( , i). Agreement: Observe that every path has a common node on it, since a path travels through f +1 nodes and one of them is good. If we then suppose that the root is not common: by Lemma 10.2.3, it must have a not-common child, that node must have a not-common child, etc. But this constructs a path from the root to a leaf with no not-common nodes, which we just proved can’t happen.