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 10 else 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)