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.