/Solutions.

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?

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?

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. Clarification added 2008-02-26: Show that the algorithm works or doesn't work for sufficiently large n; i.e., the fact that it doesn't work when n=3 shouldn't count against it if it works for all n > 12.