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.

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][ij] where ij 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.