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.

1. Agreement with partial broadcast

Suppose you have an asynchronous message-passing system that provides, in addition to the usual point-to-point message-passing operations, the ability to carry out a partial broadcast. This is a message that is guaranteed to be delivered simultaneously to at least b processes (formally, we imagine one super-delivery event in which at least b processes, chosen by the adversary, receive the message and update their states appropriately). The remaining processes do not receive the message at all. Note that as with regular messages, partial broadcasts may be delayed for a long time, but must be delivered to some set of at least b processes eventually if the sender is not faulty.

For what values of b can you solve agreement in this system with one faulty process?

1.1. Solution

Having b ≥ n/2+1 is both necessary and sufficient.

1.1.1. Upper bound

Consider the following algorithm:

procedure consensus(input):
    partial-broadcast(<id, input>)
    wait to receive <repeat(k)> from at least n/2 processes for some k
    decide k

upon receiving <id, k>:
    if this is the first partial-broadcast received:
        send <repeat(k)> to all processes

Proving validity is trivial: any value that gets sent to anybody starts out as somebody's input.

To prove termination, we need to show that some value is repeated to each process by a majority of processes. Here we use the fact that b ≥ n/2+1; so the first partial broadcast to be delivered will supply the first value to at least n/2+1 processes, at most one of which is faulty. The n/2 non-faulty processes will repeat this value to all other processes, which can then decide.

For agreement, observe that the first delivered partial broadcast reaches a strict majority of at least n/2+1 processes first. Then any other value reaches at most n/2 - 1 < n/2 processes first. So only the first value can get the majority of repeats needed to become the decision value.

1.1.2. Lower bound

Here we want to show that if b < n+1/2, we are in trouble.

The proof is basically FLP, but there are some tricky details. The main complication is that partial broadcast delivery events include a choice of the set of recipients, determined by the adversary. So we need to make sure that we can't escape a bivalent state based on which set of recipients the adversary chooses.

Lemma: Let C be a configuration and let e₀ and e₁ be deliveries of some partial broadcast to sets of processes S₀ and S₁. Then either Ce₀ and Ce₁ are both k-valent for the same value k, or there exists a set of recipients S₂ and delivery event e₂ of this partial broadcast to processes in S₂ such that Ce₂ is bivalent.

Proof: Let's suppose S₀ is 0-valent and S₁ is 1-valent (if not, rename the sets). Construct a sequence of intermediate delivery sets by (a) adding one process at a time to S₀ until we get the set of all processes, then (b) removing one process at a time until we get S₁. For each adjacent pair of sets in this sequence, there is exactly one process that can distinguish between the two delivery events, and if this one process dies none of the others can tell which occurred ; so by the same reasoning as the proof that there is an initial bivalent state we have a bivalent configuration resulting from a delivery event somewhere in this chain.

Now we run stock FLP until we get to a configuration where Ce is 0-valent (say) and Cee' is 1-valent, and derive a contradiction by case analysis.

e and e' are both ordinary message-passing events. Use FLP argument.
e is a message receipt, e' is a partial-broadcast receipt. Then Cee' and Ce'e are indistinguishable except to the recipient of e, whom we kill.
e' is a message receipt, e is a partial-broadcast receipt. Again only the message recipient can distinguish Cee' from Ce'e.
e and e' are both partial-broadcast receipts. Replace e and e' with partial-broadcast receipts d and d' that minimize overlap while maintaining the same valence (if Ced' is bivalent, then we are happy as well). We have b < n/2+1 so b+b < n+2 or b+b ≤ n+1; so it is possible to arrange these sets so that only one process is included in both. But then this is the only process that can distinguish Cdd' from Cd'd, and again after we kill this process we get our contradiction.

It follows that solving consensus in this model is impossible if b < n/2+1.

2. A linear register

Suppose you are given a collection of registers that support, in addition to the usual read and write operations, a fetch-and-add-and-multiply operation that atomically implements the following code:

procedure fetch-and-add-and-multiply(r, a, b)
    x ← read(r)
    write(r, a⋅x+b)
    return x

What is the consensus number of this fetch-and-add-and-multiply register?

2.1. Solution

The consensus number of fetch-and-add-and-multiply is ∞.

Proof: The following algorithm solves binary consensus for any number of processes, using a single fetch-and-add-and-multiply register initialized to 0.

procedure consensus(input):
    fetch-and-add-and-multiply(r, 3, input+1)
    v ← read(r)
    Let d be the first nonzero digit in the base-3 representation of v
    return d-1

This works because the first process to execute the fetch-and-add-and-multiply operation sets the leading digit of the base-3 representation to its input+1, and subsequent calls to fetch-and-add-and-multiply don't changing the leading digit (though they do shift it left). So all processes return the leading digit-1 (giving agreement), which is the input to the first process to execute fetch-and-add-and-multiply (giving validity).

3. Not entirely inspired by the Democratic presidential primary

Consider the following algorithm for solving Byzantine agreement with two input values 0 and 1 in a synchronous message-passing system with f faulty processes:

procedure Agreement(input):
    preference ← input
    for each round:
        send preference to all processes (including myself)
        receive preferences 
        let majority = majority preference (breaking ties in favor of 0)
        let multiplicity = number of occurrences of majority
        if multiplicity ≥ n-f:
            decide on majority
        else:
            preference ← majority

Prove or disprove: The above algorithm solves Byzantine agreement when f=1.

3.1. Solution

Disproof. We'll construct an execution that violates termination.

Let n be odd, and consider an initial configuration where exactly (n-1)/2 non-faulty processes start with each input 0 or 1. We will maintain the property that the non-faulty processes are evenly split. In each round, the faulty process sends 0 to (n-1)/2 processes and 1 to (n-1)/2 processes. The processes in the first set receive (n+1)/2 zeros, while the processes in the second set receive (n+1)/2 ones; thus each set adopts a different majority value as its preference. Because the Byzantine process can keep this going forever, no process every receives n-1 identical votes, so no process ever decides.