For more uptodate 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 coinflips. This corresponds to assuming an oblivious or perhaps contentoblivious 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 (all0 input => all0 output and all1 input + no failures => all1 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 stronglyconnected 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, informationlevel) pairs for all processes in the system. Initially this is (myinput, 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 epidemicfashion 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' nonnull 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]^{t1} 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}^{0}[k] = level_{j}^{0}[k] = 1 if neither i nor j equals k; if one of them is k, we get level_{that one}^{0}[k] = 0, which is still close enough.
After t rounds, consider level_{i}^{t}[k]  level_{i}^{t1}[k] and similarly level_{j}^{t}[k]  level_{j}^{t1}[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'}^{t1}[k] > level_{j}^{t1}[k]. From the induction hypothesis, level_{j'}^{t1}[k] <= level_{i}^{t1}[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. Almostmatching 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 k1 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 all1 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.