1. A new consensus protocol

Consider the following protocol for binary RandomizedConsensus using shared memory.

The shared data consists of 2n+1 registers a[1..2n+1], all initially set to ⊥.

Each process executes the following code:

preference ← input
while true do:
    read all 2n+1 registers
    if all registers have the same value v and v≠⊥:
        decide v
    if at least n+1 of the registers have the same value v and v≠⊥:
        preference ← v
    choose r uniformly at random and set a[r] ← preference

Does this algorithm solve consensus? Why or why not?

2. Version control with quorums

The day after its Subversion server catches fire, a large software company decides to implement a new version control system with replicated data stores. Using this system, a user should be able to check out (read) a document and check in (write) an update if and only if no other updates have been checked in (by anybody) since the user's last checkout. They would like to implement this system in an asynchronous message-passing system with five servers, with the guarantee that the system will continue to work as long as no more than two of the servers fail (by crashing).

Describe a mechanism for implementing this system, or show that it can't be done without additional assumptions.

3. Paxos with failure detectors

Suppose we run the basic Paxos algorithm with a failure detector, with the rule that any acceptor will reject (responding with nack and not otherwise updating their state) all messages from a proposer unless the proposer has the smallest id among all proposers that the acceptor doesn't currently suspect. Suppose also that we modify the proposer's code so that it aborts a round and tries again with a higher round number if it receives nack from or suspects a majority of acceptors. Assuming some proposer and a majority of acceptors never crash, with which of the FailureDetectors <>S, S, <>‹„P, and P will the algorithm always eventually terminate?