[FrontPage] [TitleIndex] [WordIndex

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.

2. Shared-memory causality

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

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.

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

instead of

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

2014-06-17 11:58