1. Permuted quorum systems

Consider the following strategy for spreading load evenly in a quorum system. Let S be a quorum system on n servers, and for each permutation π of the servers and quorum Q, let π(Q) be the quorum obtained by replacing each x∈Q with π(x). Let Π(S) be the set containing π(Q) for all permutations π and Q∈S.

1. Show that the load of Π(S) is always less than or equal to the load of S.

2. Show that the failure probability of Π(S) always less than or equal to the failure probability of S, assuming each server fails with independent probability p < 1/2.

3. Prove or disprove: For all quorum systems S, Π(S) is also a quorum system.

1.1. Solution

1. Since S is a quorum system, its load is at least min(|Q|)/n. Let Q be some quorum in S of minimum size, and consider the probability distribution on Π(S) that assigns equal probability to all (n choose |Q|) permutations of Q. Then by symmetry, each server has probability |Q|/n ≤ load(S) of being in the chosen quorum.
2. Since every quorum in S is also in Π(S), if Π(S) fails, so does S. It follows that the probability of failure of Π(S) is no greater than the probability of failure of S.

3. In general, Π(S) is not a quorum system. For example, suppose n = 2 with servers 0 and 1, and let S = { {0} }. Then Π(S) = { {0}, } contains two sets whose intersection is empty.

2. Shared-memory causality

Let us define a happens-before relation ⇒_S for shared memory (see also AttiyaWelch §6.1.4):

• If e and e' are events of the same process, and e precedes e' in S, then e ⇒_S e'.

• If at least one of e or e' is a write operation, and e precedes e' in S, then e ⇒_S e'.

• If there exists some event e'' such that e ⇒_S e'' ⇒_S e', then e ⇒_S e'.

Here each e is an event of of the form read(p, r, v) or write(p, r, v), where p is a process, r a register, and v a value. (We'll omit internal actions of the processes to make life easier.)

1. Show that if S is the schedule for some execution of a shared-memory system, and S' is a permutation of S such that e ⇒_S e' implies e precedes e' in S', then S' is also a schedule of some execution of the same shared-memory system.

2. Prove or disprove: Let S and S' be similar schedules of a shared-memory system; that is, let S|p = S'|p for all p, and suppose each write operation in S/S' writes a unique value that is also distinct from the initial value of the register. Then for every pair of events e, e', if e ⇒_S e', then e precedes e' in S'.

In each case, assume multi-writer multi-reader registers.

2.1. Solution

1. We need to show that S' is consistent with the behavior of both the processes and the registers. We'll do this by induction on the length of S', with the base case being an empty sequence. For a longer prefix Pe of S', assume that P is consistent with some execution. In particular, this means that P|p is a prefix of S|p for all p, and that each read operation in P returns the value of the last preceding write. Let p be the process that executes event e. Then e precedes any event in S that is not in Pe (clause 1 of the definition), so Pe|p is a prefix of S|p and e is consistent with p's programming. If e is a read operation, we also need to show that it returns the value of the last preceding write. Here we observe that clause 2 means that writes to a particular register r occur in the same order in S' as in S, and that if e is a read operation, it occurs between the same two writes in S' as in S. So in particular the last write before e in Pe prefix of S' is the same write that precedes e in S, so it returns the correct value.

2. Disproof: Let S = write(p, r, 0) write(q, r, 1) and let S' = write(q, r, 1) write(p, r, 0). Then S|p = S'|p and S|q = S'|q, and both correspond to valid executions of the same system, but write(p, r, 0) ⇒_S write(q, r, 1) (clause 2) even though they appear in the opposite order in S'

3. Snapshots in slightly less space

A data structure company hires you to implement Algorithm 30 from page 227 of AttiyaWelch. Unfortunately, they didn't budget enough room for the toggle bits, and so the critical Line 6 becomes

• Segment[i] := (d, view)

instead of

• Segment[i] := (d, view, ¬Segment[i].toggle)

Show how to modify procedure scan() so that the snapshot protocol still works.

3.1. Solution

Basic idea: Instead of checking if the toggle field changes, check if the d field changes.

In more detail: We assume a process has done an update (and increment shook etc.) if either checkHS returns true or a[j].d ≠ b[j].d in line 15 (that is, we replace the test on toggle with a test on d). Then any single update that changes the value of d will still be detected (just as it would have because of the toggle bit). An update that does not change the value of d we don't care about: if I read the same value twice from the same register, and the only intermediate writes also put the same value in, then this value is in fact present in the register from the end of my first collect to the start of my second collect, just as if there were no updates. If there are two updates, it is possible that some other value might have been briefly present, but in this case the handshake succeeds. So the same analysis as for the original snapshot algorithm applies.