Shared snapshot objects

The basic idea of this algorithm is that every process executing the scan() operations, reads all the memory values twice. If the algorithm reads exactly the same memory content twice, no other process changed a value in between and it can return the result. A process, which executes an update(i,v) operation, just update its value in the memory.

function scan()
    while true
        a[1..n] := collect;
        b[1..n] := collect;
        if (∀i∈{1, .., n} location i was not changed between the reads of it during the two collects)) then
            return b; // double collect successful
    loop
end

function update(i, v)
    M[i] := v;
end

Fig.1: One process always updates the memory, during the double collect of the other process. Thus, the scanning-process is never able to terminate.

This algorithm provides a very basic implementation of snapshot objects. It guarantees that the system proceeds, while individual threads can starve due to the behaviour of individual processes. A process P_i can prevent another process P_j from terminating a scan() operation by always changing its value, in between the two memory collects. Thus, the algorithm is lock-free, but not wait-free. To hold this stronger the property, no process is allowed to starve due to the behavior of other processes. Figure 1 illustrates the problem. While P₁ tries to execute the scan() operation, a second process P₂ always disturbs the "double-collect". Thus, the scanning process always has to restart the operation and can never terminates and starves.

The basic idea of the swmr snapshot algorithm by Afek et al. is that a process can detect whether another process changed its memory location and that processes help each other. In order to detect if another process changed its value, a counter is attached to each register and a process increases the counter on every update. The second idea is that, every process who updates its memory position also performs a scan() operation and provides its "view of the memory" in its register to other processes. A scanning process can borrow this scan result and return it.

Using this idea one can construct a wait-free algorithm that uses registers of unbounded size. A process performing an update operation can help a process to complete the scan. The basic idea is that if a process sees another process updating a memory location twice, that process must have executed a complete, linearized, update operation in between. To implement this, every update operation first performs a scan of the memory and then writes the snapshot value atomically together with the new value v and a sequence number. If a process is performing a scan of the memory and detects that a process updated the memory part twice, it can "borrow" the "embedded" scan of the update to complete the scan operation.[1]

function scan()                                         // returns a consistent view of the memory
    for j = 1 to n do moved[j] := 0 end
    while true do
        a[1..n] := collect;                             // collects (data, sequence, view) triples
        b[1..n] := collect;                             // collects (data, sequence, view) triples
        if (∀j∈{1, ..., n}) (a[j].seq = b[j].seq) then
            return (b[1].data, ..., b[n].data)          // no process changed memory
        else for  j = 1 to n do
            if a[j].seq ≠ b[j].seq then                 // process moved
                if moved[j] = 1 then                    // process already moved before
                    return b[j].view;
            else moved[j] := moved[j] + 1;
        end
    end
end function

procedure update(i,v)                        // updates the registers with the data-values, updates the sequence number, embedded scan
    s[1..n] := scan;                         // embedded scan
    ri := (v, ri.seq = ri.seq + 1, s[1..n]);
end procedure

Fig.2: Example linearization order for a single-writer multi-reader snapshot object. The first scan() can successfully perform a double-collect, while the "double-collect" of the second scan is interrupted twice by the second process. Thus, the process borrows an embedded scan.

Every register consists of a field for the data-value, the sequence number and a field for the result of the last embedded scan, collected before the last update. In each scan operation the process P_i can decide whether a process changed its memory using the sequence number. If there is no change to the memory during the double collect, P_i can return the result of the second scan. Once the process observes that another process updated the memory in between, it saves this information in the moved field. If a process P_j changed its memory twice during the execution of the scan(), the scanning process P_i can return the embedded scan of the updating process, which it saved in its own register during its update operation.

These operations can be linearized by linearizing each update() operation at its write to the register. The scan operation is more complicated to linearize. If the double collect of the scan operation is successful the scan operation can be linearized at the end of the second scan. In the other case - one process updated its register two times - the operation can be linearized at the time the updating process collected its embedded scan before writing its value to the register.[1]

One of the limitations of the presented algorithm is that it is based on an unbounded memory since the sequence number will increase constantly. To overcome this limitation, it is necessary to introduce a different way to detect whether a process has changed its memory position twice in between. Every pair of processes ${\displaystyle \langle P_{i},P_{j}\rangle }$ communicates using two single-writer single-reader (swsr) registers, which contains two atomic bits. Before a process starts to perform a "double collect", it copies the value of its partner process to its own register. If the scanner-process P_i observes after executing the "double-collect" that the value of the partner process P_j has changed in between it indicates that the process has performed an update operation on the memory.[1]

function scan()                                        // returns a consistent view of the memory
    for j=1 to n do moved[j] := 0 end
    while true do
        for j=1 to n do qi,j := rj.pj,i end
        a[1..n] := collect;                            // collects (data, bit-vector, toggle, view) triples
        b[1..n] := collect;                            // collects (data, bit-vector, toggle, view) triples
        if (∀j∈{1, ...,n}) (a[j].pj,i = b[j].pj,i = qi,j) and a[j].toggle = b[j].toggle then
            return (b[1].data, ..., b[n].data)         // no process changed memory
        else for  j=1 to n do
            if (a[j].pj,i ≠ qi,j) or (b[j].pj,i ≠ qi,j) or (a[j].toggle ≠ b[j].toggle) then // process j performed an update
                if moved[j] = 2 then                   // process already moved before
                    return b[j].view;
            else moved[j] := moved[j] + 1;
        end
    end
end function

procedure update(i,v)                        // updates the registers with the data-value, "write-state" of all registers, invert the toggle bit and the embedded scan
    for j = 1 to n do f[j] := ¬qj,i end
    s[1..n] := scan;                         // embedded scan
    ri := (v, f[1..n], ¬ri.toggle, s[1..n]);
end procedure

The unbounded sequence number is replaced by two handshake bits for every pair of processes. These handshake bits are based on swsr registers and can be expressed by an matrix M, where process P_i is allowed to write to row i and is allowed to read the handshake bits in a column i. Before the scanning-process performs the double-collect it collects all the handshake bits from all registers, by reading its column. Afterwards, it can decide whether a process changed its value during the double value or not. Therefore, the process just has to compare the column again with the initially read handshake bits. If only one process P_j has written twice, during the collection of P_i it is possible that the handshake bits do not change during the scan. Thus, it is necessary to introduce another bit called "toggle bit", this bit is changed in every write. This makes it possible to distinguish two consecutive writes, even though no other process updated its register. This approach allows to substitute the unbounded sequence numbers with the handshake bits, without changing anything else in the scan procedure.

While the scanning process P_i uses a handshake bit to detect whether it can use its double collect or not, other processes may also perform update operations. As a first step, they read again the handshake bits provided by the other processes, and generate the complement of them. Afterwards these processes again generate the embedded scan and save the updated data-value, the collected - complemented - handshake bits, the complemented toggle bit and the embedded scan to the register.

Since the handshake bits equivalently replace the sequence numbers, the linearization is the same as in the unbounded memory case.

The construction of multi-writer multi-reader snapshot object assumes that n processes are allowed to write to any location in the memory, which consists of m registers. So, there is no correlation, between process id and memory location anymore. Therefore, it is not possible anymore to couple the handshake bits or the embedded scan with the data fields. Hence, the handshake bits, the data memory and the embedded scan cannot be stored in the same register and the write to the memory is not an atomic operation anymore.

Fig.3: Shows an exemplary linearization for a multi-writer multi-reader snapshot object

Therefore, the update() process has to update three different registers independently. It first has to save the handshake bits it reads, then do the embedded scan and finally saves its value to the designated memory position. Each write independently appears to be done atomically, but together they are not. The new update() procedure leads to some changes in the scan() function. It is not sufficient anymore to read the handshake bits and collect the memory content twice. In order to detect a beginning update process, a process has to collect the handshake bits a second time, after collecting the memory content.

If a double-collect fails, it is now necessary that a process sees another process moving three times before borrowing the embedded scan. Figure 3 illustrates the problem. The first double-collect fails, because an update process started before the scan operation finishes its memory-write during the first double collect. However, the embedded scan of this write is performed and saved, before P₁ starts scanning the memory and therefore no valid Linearization point. The second double-collect fails, because process P₂ starts a second write and updated its handshake bits. In the swmr scenario, we would now borrow the embedded scan and return it. In the mwmr scenario, this is not possible because the embedded scan from the second write is still not linearized within the scan-interval (begin and end of operation). Thus, the process has to see a third change from the other process to be entirely sure that at least one embedded scan has been linearized during the scan-interval. After the third change by one process, the scanning process can borrow the old memory value without violating the linearization criterion.