1
$\begingroup$

Background:

$K$-atomicity is a consistency condition meaning that a read operation can return one of the values written by the last $k$ preceding writes in an order consistent with real time. It is a relaxed version of atomicity, tolerating limited staleness.

Given $m$ instances of $k$-atomic single-writer registers, one can construct a $k'$-atomic multi-writer register which supports $m$ writers. In the paper "Byzantine and Multi-writer K-Quorums [@DISC'2006]", the authors show that $k'$ cannot be arbitrarily low. They first obtain, by an illustrative scenario, a lower bound of $k' = \big( (2m-1)(k-1) + 1 \big)$ and then present a multi-writer construction which achieves $k' = \big( (2m-1)(k-1) + m \big)$.

Multi-writer construction:

The multi-writer construction uses $m$ instances of the $k$-atomic single-writer registers, one for each writer $w_i$. It uses approximate vector timestamps to compare the written values from different writers. Each writer $w_i (1 \le i \le m)$, maintains a local virtual clock $lts_i$, which is incremented by 1 for each write.

To perform a multi-writer write operation (mw-write(i,val)), the writer $w_i$ first reads from all the underlying $k$-atomic single-writer registers, obtaining $m$ vector timestamps. It thens calculate an approximate vector timestamps $ats$, by setting $ats[j] (j \neq i)$ equal to the largest value for entry $j$ among the received $m$ vector timestamps and setting $ats[i]$ equal to $lts_i + 1$. The value, along with the timestamp $ats$, is finally written to the $k$-atomic single-writer register for this writer.

static lts_i = 1                                            
void mw-write(i,val):                                     mw-read(): return <val,ts>   
    for j = 1 to m                                            for j = 1 to m
        <val_j, ts_j> = sw-read(j)                                <val_j, ts_j> = sw-read(j)

    ats[j] = max_p {ts_p[j]} for j != i                       apply elimination rules ...
    ats[i] = lts_i++                                          and return some value

    sw-write(i,<val,ats>)

To perform a read operation (mw-read()), a reader reads from all the underlying $k$-atomic single-writer registers, obtaining $m$ vector timestamps. Two elimination rules are then applied to choose some value (along with its timestamp) to return.

The case $k=3, m=2$ and my problem:

Consider the following possible execution of this multi-writer construction when taking $k=3, m=2$. As shown in the figure, the dashed arrows denote which vector timestamps (value is omitted) are obtained when the writer performs sw-read operations on the underlying $k$-atomic single-writer registers. Two writers interleave in a "highly concurrent" way. Concurrent writes are put in the same row. In particular, the write of $\langle 4,3 \rangle$ by Writer 1 is concurrent with the writes of $\langle 1,4 \rangle, \langle 1,5 \rangle, \langle 1,6 \rangle$ by Writer 2. According to the multi-writer construction, the mw-read operation by Writer 1 first reads from the two underlying $k$-atomic single-writer registers, obtaining two vector timestamps $\langle 4,3 \rangle$ and $\langle 1,6 \rangle$.

what_is_the_staleness_(3,2) http://i1.tietuku.com/ff708c97cf73f760.jpg

My problem: Assuming now that the mw-read operation by Writer 1 simply returns any one of the two vector timestamps. Then what is the staleness of the mw-read operation in this execution?

In my opinion, if we schedule the writes to take place at the same instance as it is scheduled to take place in the underlying $k$-atomic single-writer register (i.e., the code line sw-write(i,<val,ats>)), the write of $\langle 4,3 \rangle$ will be ordered after the write of $\langle 1,5 \rangle$ and the staleness of mw-read is guaranteed to be less than or equal to 6 (ordering $\langle 1,5 \rangle$ before $\langle 4,3 \rangle$ which is before $\langle 1,6 \rangle, \langle 5,6 \rangle, \langle 4,7 \rangle, \langle 6,6 \rangle, \langle 5,8 \rangle$ and returning $\langle 4,3 \rangle$).

However, because all the three mw-write operations of $\langle 1,4 \rangle, \langle 1,5 \rangle, \langle 1,6 \rangle$ by Writer 2 interleave with the mw-write of $\langle 4,3 \rangle$ by Writer 1, it is also legal to order the latter write of $\langle 4,3 \rangle$ before the former three. In this circumstance, the staleness of the mw-read can be 8 (also returning $\langle 4,3 \rangle$).

I am quite confused about the two above-mentioned arguments. Which is correct? How to identify the staleness of this execution of the multi-writer construction?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.