Weak Consistency Sample Clauses

Weak Consistency. If an honest party outputs (vk, sid, v, 2), then every honest party outputs (vk, sid, v, g) with g ∈ {1, 2}. We implement 3-round gradecast over 3-graded gossip in Protocol 2. Protocol 2: πgradecast The protocol is parameterized by a maximum message size L and uses the protocol

Weak Consistency. Suppose an honest party outputs a message (vk, sid, v, 2) at round r + 3. This means the party received a message (vk, sid, (r, v), 3) at round r+1, and it did not receive an equivocation proof (vk, sid, ⊥, ·) up to round r + 3. By 3-graded gossip consistency, every other honest party must have received (vk, sid, (r, v), g) or (vk, sid, ⊥, g) by round r + 2, for g ∈ {2, 3}; however, it cannot be (vk, sid, ⊥, g) since then (by 3-graded gossip consistency ) every honest party must have received (vk, sid, ⊥, g′) by round r + 3 (for g′ > 0). Thus, every honest party must have received (vk, sid, (r, v), g) by round r + 2, and must have output either (vk, sid, v, 1) or (vk, sid, v, 2) at round r + 3. Thus, weak consistency is satisfied. Observing that the gradecast protocol makes only a single call to graded gossip, and no other communication is required, gives us a simple bound on the communication complexity of Protocol 2: Lemma 3.10 (Communication Complexity). Let BCost(L) be the communication complexity for graded gossip with maximum message size of L bits, and let |r| a bound on the encoding of the communication round. Then, the communication complexity of πgradecast (Protocol 2) is at most BCost(|r| + L).

Weak Consistency. If an honest player vi decides on yi ∈ {0, 1} then every other honest vj decides on yi ∈ {yi , ⊥}. Protocol:WeakConsensus(x1 . . . xn) → (y1 . . . yn) 1 Every vi ∈ V sends xi to all vj . Let cj be the copies of a message m ∈ {0, 1} received by player vj in this round.

Weak Consistency. Let vi , vj ∈ H and yi = 0. Thus ci ≥ n − t. That means that at least n − 2t honest players sent him this value. Consequently 1 cj ≥ n − 2t ⇒ cj = n − n + 2t = 2t < n − t So vj computes either yj = 0 or yj =⊥. Every vi ∈ V computes yi and the grade value gi ∈ {0, 1}. Graded Consistency If vi ∈ H decides on yi ∈ {0, 1} with gi = 1 then every other vj ∈ H decides on yj = xx . Every vi ∈ V computes yi and the grade value gi ∈ {0, 1}. Graded Consistency If vi ∈ H decides on yi ∈ {0, 1} with gi = 1 then every other vj ∈ H decides on yj = xx . Protocol:GradedConsensus(x1, . . . , xn) → ((y1, g1), . . . , (yn, gn)) 1 (z1, . . . , zn) := WeakConsensus(x1, . . . , xn) 2 Every vi ∈ V sends zi to all vj . 3 Every vj computes: 0 else , gj = 0 else .1 if cj > cj .1 if cj ≥ n − t 4 Every vj ∈ V returns (yj , gj ) Proof.