Note: You are looking at a static copy of the former PineWiki site, used for class notes by James Aspnes from 2003 to 2012. Many mathematical formulas are broken, and there are likely to be other bugs as well. These will most likely not be fixed. You may be able to find more up-to-date versions of some of these notes at http://www.cs.yale.edu/homes/aspnes/#classes.

# 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)