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

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

## 1.1. Solution

Here is an easy solution using a snapshot: for write operations, have each process write its value to its own segment (writing

*fail*if called twice by the same process), and for a read take a snapshot and return*fail*if some segment contains*fail*or two or more segments are occupied.It is possible to build a write-once register using only O(log n) registers. Use one multiwriter register

`value`to hold the value of the register, and a 2×⌈lg n⌉ array of bits`present`to mark which processes have written a value to the register. To write a value v (for the first time) as process i, write 1 to each bit`present`[j][i_{j}] where i_{j}is the j-th bit of id i expressed in binary, and then write v to`value`. For subsequent writes, write 1 to`present`[0][0] and`present`[0][1]. To read the register, perform a double-collect snapshot on both`value`and the`present`array (note this eventually terminates because after 2n writes there are no further changes to the array, and each write operation only changes the array a finite number of times). If the`present`array contains exactly one 1 in each row`present`[j] and`value`is not null, return`value`. If value is null, return*empty*. If`present`contains no ones in some row, return*empty*. If it contains two ones, return*fail*.To show this is linearizable, assign to each read operation some time between its two equal collects (because we are doing double-collect and not something more clever, the values in the registers at this time will be exactly equal to the values collected. Assign to each write operation the first time during its execution at which

`present`[j][0] and`present[j][1]`are both set for some j, or the time at which it writes`value`if this event does not occur; if this assigns the same time to multiple writes, order those writes arbitrarily with respect to each other. A read operation returns*fail*it observes`present`[j][0] and`present`[j][1] both set for some j, which is correct because any such read is linearized after at least two writes. It returns v if`value`contains v and there are no collisions in`present`, which again is correct because it is linearized after exactly one write, which wrote v to`value`(if there are two writes both serialized before the read, they must have written colliding bits in`present`). It returns*empty*if no process has yet written to`value`and no collision has occurred, which implies that no write is linearized before it; again this is correct.

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

## 2.1. Solution

Disproof: Consider a pair of processes whose original ids differ only in the last bit, and run them through the splitters in lockstep, so that neither stops on any splitter on the O(log N)-long path on which their original id bits agree. Then a collect operation must follow this same path to find the two processes, giving a cost of Ω(log N) when k = O(1). (In general, with k/2 such pairs, for reasonably small k, we can force the collect to pay Ω(k log N)). Since this cost depends on N, it's not adaptive.