For more up-to-date notes see http://www.cs.yale.edu/homes/aspnes/classes/465/notes.pdf.

In IndistinguishabilityProofs, we saw a proof that we can't solve the coordinated attack problem. But maybe we want to solve it anyway. The solution is to change the problem.

1. Randomized coordinated attack

Like standard coordinated attack, but with less coordination. Specifically, we'll allow the processes to flip coins to decide what to do, and assume that the communication pattern (which messages get delivered in each round) is fixed and independent of the coin-flips. This corresponds to assuming an oblivious or perhaps content-oblivious adversary (see TypesOfAdversaries). We'll also relax the Agreement property to only hold with some high probability:

Randomized Agreement

For any adversary A, Pr[some process decides 0 and some other process decides 1 | B] <= epsilon.

Validity (all-0 input => all-0 output and all-1 input + no failures => all-1 output) and Termination (everybody decides within r rounds) are as before.

2. An algorithm

Here's an algorithm that gives epsilon = 1/r. (See LynchBook Section 5.2.2 for details). Simplifying assumption is that network is complete, although strongly-connected network with r >= diameter also works.

• First part: tracking information levels
  • Each process tracks its "information level," initially 0. The state of a process consists of a vector of (input, information-level) pairs for all processes in the system. Initially this is (my-input, 0) for itself and (null, -1) for everybody else.
  • Every process sends its entire state to every other process in every round.

  • Upon receiving a message m, process i stores any inputs carried in m and, for each process j, sets level_i[j] to max(level_i[j], level_m[j]). It then sets its own information level to max_j(level_i[j])+1.

• Second part: deciding the output
  • Process 1 chooses a random key value uniformly in the range [1,r].
  • This key is distributed epidemic-fashion to all other processes.

  • A process decides 1 at round r iff it knows the key, its information level >= key, and all inputs are 1.

2.1. Why it works

Termination

immediate from the algorithm.

Validity

• If all inputs are 0, no process sees all 1 inputs (technically requires an invariant that processes' non-null views are consistent with the inputs, but that's not hard to prove.)
• If all inputs are 1 and no messages are lost, then information level of each process after k rounds is k (prove by induction) and all processes learn key and all inputs (immediate from first round). So all processes decide 1.

Randomized Agreement

• First prove a lemma: Define level_i^t[k] to be the value of level_i[k] after t rounds. Then for all i, j, k, t, (1) level_i[j]^t <= level_j[j]^t-1 and (2) | level_i[k]^t - level_j[k]^t | <= 1. As always, the proof is by induction on rounds. Part (1) is easy and boring so we'll skip it. For part (2), we have:

  • After 0 rounds, level_i⁰[k] = level_j⁰[k] = -1 if neither i nor j equals k; if one of them is k, we get level_{that one}⁰[k] = 0, which is still close enough.

  • After t rounds, consider level_i^t[k] - level_i^t-1[k] and similarly level_j^t[k] - level_j^t-1[k]. It's not hard to show that each can jump by at most 1. If both deltas are +1 or both are 0, there's no change in the difference in views and we win from the ind hyp. So the interesting case is when level_i[k] stays the same and level_j[k] increases or vice versa.

  • There are two ways for level_j[k] to increase:

    • If j != k, then j received a message from some j' with level_j'^t-1[k] > level_j^t-1[k]. From the induction hypothesis, level_j'^t-1[k] <= level_i^t-1[k] + 1 = level_i^t[k]. So we are happy.

    • If j = k, then j has level_j^t[j] = 1 + max_{k != j} level_j^t[k] <= 1 + level_j^t[i] <= 1 + level_i^t[i]. Again we are happy.

• Note that in the preceding, the key value didn't figure in; so everybody's level at round r is independent of the key.

• So now we have that level_i^r[i] is in { l, l+1 }, where l is some fixed value uncorrelated with key. The only way to get some process to decide 1 while others decide 0 is if l+1 >= key but l < key. (If l = 0, a process at this level doesn't know key, but it can still reason that 0 < key since key is in [1,r].) This can only occur if key = l+1, which occurs with probability at most 1/r since key was chosen uniformly.

3. Almost-matching lower bound

Lower bound is Pr[disagreement] = epsilon >= 1/(r+1).

Proof

• Define level_i^t[k] as in previous algorithm (whatever the real algorithm is doing).

• Now show Pr[i decides 1] <= epsilon * (level_i^r[i] + 1) by induction on level_i^r[i]

  • If level_i^r[i] = 0, real execution is indistinguishable (to i) from execution in which some other process j starts with 0 and receives no messages at all. In that execution, j must decide 0 or risk violating Validity. So i decides 1 with probability at most epsilon (from the disagreement bound).

  • If level_i^r[i] = k > 0, real execution is indistinguishable (to i) from execution in which some other process j only reaches level k-1 and thereafter receives no messages. From the induction hypothesis, Pr[j decides 1] <= epsilon*k in that pruned execution, and so P[i decides 1] <= epsilon*(k+1) in the pruned execution. But by indistinguishability, Pr[i decides 1] <= epsilon*(k+1) in the original execution.

• In the all-1 input with no messages lost, level_i^r,,[i] = r and Pr[i decides 1] = 1 (by Validity). So 1 <= epsilon(r+1) => epsilon >= 1/(r+1).

4. What's really going on here

See CommonKnowledge.

---

CategoryDistributedComputingNotes