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.
- Show that the load of Π(S) is always less than or equal to the load of S.
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.
- Prove or disprove: For all quorum systems S, Π(S) is also a quorum system.
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'. Clarification added 2008-04-10: This case applies only if e and e' are both operations on the same register.
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.)
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.
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.
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.