Note: You are looking at a static copy of the former PineWiki site, used for class notes by James Aspnes from 2003 to 2012. Many mathematical formulas are broken, and there are likely to be other bugs as well. These will most likely not be fixed. You may be able to find more up-to-date versions of some of these notes at http://www.cs.yale.edu/homes/aspnes/#classes.

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

Here we'll consider synchronous agreement algorithm with stopping failures. For lower bound on rounds, see IndistinguishabilityProofs. For communication failures, see IndistinguishabilityProofs for the impossibility proof and RandomizedCoordinatedAttack for protocols that work some of the time. We'll also consider Byzantine failures, where a process deviates from its programming by sending arbitrary messages, but mostly just to see how crash-failure algorithms hold up; for algorithms designed for a Byzantine model, see ByzantineAgreement.

1. Problem definition

Usual synchronous model: n processes with binary inputs and binary outputs. Up to f processes may fail at some point, causing loss of one or more outgoing messages in round of failure and all outgoing messages thereafter. For the positive result, we will ask for

Agreement: All non-faulty processes decide the same value.
Validity: If all nonfaulty processes start with the same input, they all decide it.
Termination: All nonfaulty processes eventually decide.

Validity here is stronger than the version used in the lower bound, but the lower bound still applies: we can't do this in less than f+1 rounds.

So let's do it in exactly f+1 rounds. There are two standard algorithms, one of which generalizes to Byzantine processes under good conditions.

2. Solution: Flooding

See AttiyaWelch §5.1.3 or LynchBook §6.2.1. Assumes very trustworthy processes. Each process keeps a set of (process, input) pairs, initially just {(my-id, my-input)}. At round r I broadcast my set to everybody and take the union of my set and all sets I receive. At round f+1 I decide on f(S) where f is some fixed function from sets of process-input pairs to outputs, e.g. take the input with the smallest process-id attached to it, take the max of all known input values, or take the majority of all known input values.

Lemma: After f+1 rounds, all nonfaulty processes have the same set.
Proof: Let S_i^r be the set of process i after r rounds. What we'll really show is that if there are no failures in round k, then S_i^r = S_j^r = S_i^k+1 for all i, j, and r > k. To show this, observe that no faults in round k means that all processes that are still alive at the start of round k send their message to all other processes. Let L be the set of live processes in round k. At the end of round k, for i in L we have S_i^k+1 = ∪_j∈L S_j^k = S. Now we'll consider some round r = k+1+m and show by induction on m that S_i^k+m = S; we already did m = 0, so for larger m notice that all messages are equal to S and so S_i^k+1+m is the union of a whole bunch of S's. So in particular we have S_i^f+1 = S (since some failure-free round occured in the preceding f+1 rounds) and everybody decides the same value f(S).

Flooding depends on being able to trust second-hand descriptions of values; it may be that process 1 fails in round 0 so that only process 2 learns its input. If process 2 can suddently tell 3 (but nobody else) about the input in round f+1—or worse, tell a different value to 3 and 4—then we may get disagreement. This remains true even if Byzantine processes can't fake inputs (e.g., because an input value is really a triple (i, v, signature(v)) using an unforgeable digital signature)—the reason is that a Byzantine process could horde some input (i, v, signature(v)) until the very last round and then deliver it to only some of the non-faulty processes.

3. Solution: Exponential information gathering

See AttiyaWelch §5.2.4 or LynchBook §6.2.3. Not really an improvement on flooding for crash failures, but it can be used as a basis for building an algorithm for ByzantineAgreement.

Idea again is that we will do a lot of gossiping. But now my state is no longer just a flat set of inputs, but a tree describing who I heard what from. We build this tree out of pairs of the form (id-sequence, input) where id-sequence is a sequence of intermediaries with no repetitions and input is some input. My state at each round is just a set of such pairs.

Initial state is (< >, my-input).

At round r, process i broadcasts all pairs (w, v) where |w| = r and i does not appear in w (these restrictions make the algorithm slightly less exponential). Upon receiving (w, v) from j, i adds (wj, v) to its list. If no message arrives from j in round r, i adds (wj, ⊥) to its list for all non-repeating w with |w| = r (this step can also be omitted).

Tree structure is obtained by letting w be the parent of wj for each j.

At round f+1, apply some fixed decision rule to the set of all values that appear in the tree (e.g. take the max, or decide on a default value v₀ if there is more than one value in the tree). That this works follows pretty much immediately from the fact that the set of node labels propagates just as in the flooding algorithm (which is why EIG isn't really an improvement). But there are some complications from the messages that aren't sent due to the i-not-in-w restriction on sending. So we have to write out a real proof. Below is basically just following LynchBook.

Let val(w, i) be the value v such that (w, v) appears in i's list at the end of round f+1. We don't worry about what earlier round it appears in because we can read that round off of |w|+1.

3.1. Basic invariants

val(< >, i) = i's input.
either val(wj, i) equals val(w, j) or val(wj, i) = ⊥ and j didn't send a message in round |w|+1.

These are trivial.

3.2. Stronger facts

If val(xjy, i) ≠ ⊥ then val(x, j) = val(xjy, i). Apply invariant inductively.
If val(w, i) ≠ ⊥ then it equals val(< >, j) for some j. Either w = < > and we win or apply previous to w = jy.
If val(w, i) ≠ ⊥ then there is some w' that doesn't contain i such that val(w', i) = val(w, i). Let val(w, i) = v. If w doesn't contain i we are done, otherwise w = w'iy for some w', y and val(w', i) = v.

3.3. The payoff

Let S_i^r be the set of values in i's list after round r. We'll show that S_i^f+1 = S_j^f+1 for all non-faulty i, j. Let v be in S_i^f+1. Then v = val(w, i) for some w that doesn't contain i (w here is really w' from before). If |w| <= f, then i sends (w, v) to j at round |wi| and so val(wi, j) = v. Otherwise if |w| = f+1, w = xky for some non-faulty k, and from the first stronger fact we have val(x, k) = v. Since k is non-faulty, it sends (x, v) to both i and j in round |x| and we get val(xk, j) = v. We've just shown v in S_i^f+1 implies v in S_j^f+1, and by symmetry the converse holds, so the sets are equal.

This is a lot of work to avoid sending messages that contain my own id! However, by tacking on digital signatures, we can solve ByzantineAgreement in the case where f < n/2: see LynchBook §6.2.4 for details.

3.4. The real payoff

Run the same algorithm in a Byzantine system with n > 3f processes (treating bogus-looking messages as nulls), but compute the decision value by taking recursive majorities of non-null values down the tree. Details are in ByzantineAgreement.

4. Variants

So far we have described binary consensus, since all inputs are 0 or 1. We can also allow larger input sets. With crash failures, this allows a stronger validity condition: the output must be equal to some input. Note that this stronger condition doesn't work if we have Byzantine failures. (Exercise: why not?)

CategoryDistributedComputingNotes