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.

1.1. Solution

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

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