1. A leader election problem

Consider the following requirements for leader election in a deterministic asynchronous message-passing system with crash failures and failure detectors:

1. At any time, at most one process can consider itself leader. (This is a reflected in the process's internal state, and it is not necessary that other processes know who the leader is.)
2. If a process decides it is the leader, it remains the leader until it crashes.
3. If no process considers itself to be the leader and there is at least one non-faulty process, then eventually some process decides it is the leader.

Show that:

1. It is possible to solve this form of leader election using a P failure detector.
2. It is not possible to solve this form of leader election using only an ⋄S failure detector.

2. A less logical clock

A system designer decides that incrementing a process's Lamport clock whenever the process sends a message or performs a local operation is wasteful, and implements instead an 'amport clock that is only updated upon receipt of a message. More precisely, each process maintains a local clock value, initially 0, which it appends to all outgoing messages. Upon receiving a message with clock value t, a process sets its own clock to max(old value, t+1).

Suppose now that we try to take a snapshot using an 'amport clock: we pick a time t, and for each process we record the state it was in before the first time it sets its clock greater than t. Under the assumption that every process eventually sets its clock greater than t, show either (a) that the resulting vector of local states is consistent with a global configuration in some execution indistinguishable by any process from the actual execution; or (b) that there is some execution that yields a vector that is not consistent with any such global configuration.

3. A less probabilistic quorum system

Consider the following probabilistic quorum system, which is desiged to reduce the number of random bits needed to specify a quorum. Organize p² servers into a p×p grid, where p is prime, so that each server gets coordinates (i,j) where i and j are both in the range 0...p-1. To choose a quorum Q, pick values a and b uniformly and independently at random from 0...p-1, and let Q = { (x,ax+b mod p) | x ∈ 0...p-1 }. Note: missing mod p added 2005-12-02.

1. What is the probability that two such randomly-chosen quorums intersect?
2. What is the load of this quorum system? I.e., what is the maximum over all servers of the probability that that server is included in a randomly-chosen quorum?
3. What is the fault-tolerance of this system? I.e., what is the minimum number of servers that must fail to cause all quorums to include at least one failed server?