Exponential information gathering gets Sample Clauses

Exponential information gathering gets n = 3f +1 The idea of exponential information gathering is that each process will do a lot of gossiping, but now its state is no longer just a flat set of inputs, but a tree describing who it heard what from. We build this tree out of pairs of the form (path, input) where path is a sequence of intermediaries with no repetitions and input is some input. A process’s state at each round is just a set of such pairs. At the end of f +1 rounds of communication (necessary because of the lower bound for crash failures), each non-faulty process attempts to untangle the complex web of hearsay and second-hand lies to compute the same decision value as the other processes. This technique was used by Pease, Shostak, and Lamport [PSL80] to show that their impossibility result is tight: there exists an algorithm for Byzantine agreement that runs in f +1 synchronous rounds and guarantees agreement and validity as long as n ≥ 3f + 1. → {⟨⟨⟩ ⟩} 1 S , input 2 for round 0 .. .f do {⟨ ⟩ | ⟨ ⟩∈ Λ | | Λ /∈ } 3 Send xi, v x, v S x = round i x to all processes 4 upon receiving SÕ from j do // Filter out obviously bogus tuples 5 if 6 ⟨xjÕ, v⟩∈ SÕ : |x| = round Λ jÕ = j then 6 S → S ∪ SÕ // Compute decision value 7 for each path w of length f +1 with no repeats do 8 if w, v S for some v then 9 Let valÕ(w, i) = v 11 Let valÕ(w, i) = 0 12 for each path w of length f or less with no repeats do 13 Let valÕ(w, i) = majorityj/œw val(wj, i) 14 Decide valÕ(⟨⟩ , i) 10.1: Exponential information gathering. Code for process i. The algorithm is given in Algorithm 10.1. The communication phase is just gossiping, where each process starts with its only its input and forwards any values it hears about along with their provenance to all of the other processes. At the end of this phase, each process has a set of pairs of the form (path, value) where path spans all sequences of 0 to f +1 distinct ids and value is the input value forwarded along that path. We write val(w, i) for the value stored in i’s list at the end of the protocol that is associated with path w. Because we can’t trust these val(w, i) values to be an accurate description of any process’s input if there is a Byzantine process in w, each process computes for itself replacement values valÕ(w, i) that use majority voting to try to get a more trustworthy picture of the original inputs.