How to Define and Implement (Single-Writer) K-Atomic Snapshot Object?

Question

I am trying to motivate, define, and implement $K$-atomic snapshot object. To this aim, I first give some basic definitions on atomic snapshot object and $K$-atomic object. Then, I will give my understanding of $K$-atomic snapshot object and present my problems.

Atomic Snapshot Object:

In the paper "Atomic Snapshots of Shared Memory", the authors consider atomic snapshot objects —— shared objects partitioned into segments. For the single-writer atomic snapshot object, each segment belongs to a different processor and is written separately, but all segments can be read at once by any processor.

The sequence specification of an atomic snapshot object provides two kinds of operations for each user $i, 0 \le i \le n-1$:

• A $scan_i$ invocation whose response is $return_i(V)$, where $V$ is an $n$-element vector called a view with a value for each segment, and
• An $update_i(d)$ invocation whose response is $ack_i$, where $d$ is the data to be written to $p_i's$ segment.

A sequence of $scan$ and $update$ operations satisfies the atomic snapshot semantics means that, for each $V$ returned by a $scan$ operation, $V[i]$ equals the value written by the latest preceding $update_i$ operation, for all $i$.

$K$-Atomic Object:

In the paper On the Availability of Non-strict Quorum Systems, $K$-atomic object is introduced. Different from the classical atomic object (see Sharing Memory Robustly in Message-Passing Systems), in a system with $K$-atomic semantics,

there exists an order of the operations that is consistent with real time order and such that the values returned by a read operation is equal to one of the values written by the last $K$ preceding writes in the order.

Problem 1: How to Define $K$-Atomic Snapshot Object?

$K$-atomic object is a relaxation (or a generalization) of classical atomic object, which is actually $1$-atomic object.

So based on the two concepts of $K$-atomic object and atomic snapshot object, can we define, in a reasonable manner, the $K$-atomic snapshot object?

One possible trial is to relax the timeliness of the snapshot:

A sequence of $scan$ and $update$ operations satisfies the $K$-atomic snapshot semantics means that, for each $V$ returned by a $scan$ operation,

• $V[i]$ equals one of the values written by the last $K$ preceding $update_{i}$s, for all $i$, and

• there exists some time before the $scan$ operation at which $V[i]$ equals the value written by its latest preceding $update_{i}$, for all $i$.

Problem 2: Do you know or can you figure out some other reasonable definitions of $K$-atomic snapshot object?

Any comments, any suggestions, and any related literature references are welcomed. Also, I appreciate the idea of implementation of the $K$-atomic snapshot object defined above myself (if you think it is OK).

Answer 1

Regarding Problem 1: I think the first part of the definition is fine. The second item (about the time before $scan$) is not clear to me; More specifically, the order of quatifiers: is it $\exists time: \forall i$ or $\forall i: \exists time$ ? I guess the first, because in the second I don't see why it is necessary. But definitions should not need guessing ;-)

Regarding Problem 2: In principle there is two ways of looking at $K$. You can consider the last $K$ updates on a per item level or the last $K$ updates globally. The other choice is (already mentioned above) whether to require a point in time when the memory actually had the value returned by $scan$ (the $\exists time: \forall i$ case above) or whether not to require such a point.

A general comment: What happens when every process just updates $K$ times and scans until two scans are equal. Wouldn't that (trivially) implement ($1$-)atomic snapshot memory? If that is the case then the whole idea of $K$-atomic snapshpot memory could be hard to sell.