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. Write-once registers

Suppose we want to implement a write-once register, where a read operation returns either empty (if no write has previously been done to the register), a value (if exactly one write has previously been done), or fail (if two or more writes have previously been done to the register).

1. Show that there is a linearizable wait-free implementation of write-once registers from atomic registers.
2. Prove or disprove: any linearizable wait-free implementation of write-once registers for n processes from (multiwriter) atomic registers uses Ω(n) registers.

# 2. A deterministic adaptive collect

Suppose we modify the Attiya-Kuhn-Wattenhofer-Wattenhofer collect (see AdaptiveCollect) to use original ids instead of random bits to decide which way to go in the binary tree. That is, we assume N = O(n), build a binary tree of splitters with N leaves, and at each splitter at depth i, if a process does not stop, it goes left if the i-th bit in its original id is 0 and right if the i-th bit in its original id is 1, marking the node it passes through in either case. For a collect, we do depth-first search following the marked nodes to find all the splitters owned by active processes.

Prove or disprove: the preceding algorithm gives a deterministic collect protocol that is adaptive to total contention.

2014-06-17 11:58