Graded agreement Sample Clauses

Graded agreement. Suppose node Pi output (sid, v, g) and node Pi′ output (sid, v′, g′). ≥ ̸ ≥ Case 1: g = 2 or g′ = 2. Assume without loss of generality that g = 2 (the other case is symmetric). In this case, Xx received (sid, r, v, 4) from πthresh-gossip at round r + 1; hence, by the graded gossip property of 4-graded f-threshold-gossip, Pi′ received (sid, r, v, g′′) by round r + 2, for g′′ 3. Further, Pi′ cannot have received any (sid, r, v′′′, g′′′) for v′′′ = v and g′′′ 2 by round r+3, since then by the graded gossip property Pi would have received (sid, r, v′′′, g′′′′) by round r + 4 for g′′′′ ≥ 1; hence, would not have output with g = 2. Thus, Pi′ must output either (sid, v, 1) or (sid, v, 2). Case 2: g = 1 and g′ = 1. In this case Pi received (sid, r, v, g′′) from πthresh-gossip by round r + 2, for g′′ ≥ 3. By the graded gossip property of 4-graded f-threshold-gossip, Pi′ received (sid, r, v, g′′′) from πthresh-gossip up to round r + 3, for g′′′ ≥ 2. But this implies v′ = v, otherwise Pi′ would not have output (sid, v, 1). Case 3: g = 0 and g′ ≤ 1, or g ≤ 1 and g′ = 0. In this case, graded agreement is trivially satisfied.

Graded agreement. For every two honest parties Pi and Pi′ : if Pi outputs (sid, v, g) and Pi′ outputs (sid, v′, g′), then • |g − g′| ≤ 1 • v′ ∈ {v, ⊥} or v ∈ {v′, ⊥} • If g = 2 then v′ = v For any f -faulty adversary, and assuming the number honest parties is at least f + 1, we can construct 4-round graded crusader agreement from 4-graded f -threshold gossip:

Graded agreement. If a correct process pi returns v and another correct process pj { } returns w then v = w.