<p>Regarding <strong>Problem 1</strong>: 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 ;-)</p>

<p>Regarding <strong>Problem 2</strong>: 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.</p>

<p>A <strong>general</strong> 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. </p>

CC BY-SA 3.0
2013-10-27T09:24:56.940Z
Regarding **Comment 1:** it is $\exists time : \forall i$. Regarding **Comment 2:** I agree with you that there is a possible definition in which no a time point when the memory actually had the value returned by $scan$ exists. Actually, [ZooKeeper](https://www.usenix.org/legacy/event/usenix10/tech/full_papers/Hunt.pdf) implements it and calls it _fuzzy snapshot_. However, theoretically, I am more interested in the definition which requires such points. AndI think both its computational power and implementations will be a challenge.
hengxin
CC BY-SA 3.0
2013-10-27T09:43:34.950Z
**Regarding general comment:** Of course, we can always implement (1-)atomic snapshot objects. However, maybe weaker versions are enough sometimes (e.g., as checkpoints for recovery). If we can implement $K-$atomic snapshot objects more efficiently, it is maybe useful. As for its computational power, can we relate it to $K-$mutual exclusion or $K-$set agreement (just my guess)? What do you think of it?
hengxin
CC BY-SA 3.0
2013-10-24T09:53:33.590Z
2013-10-25T14:22:50.870Z
2013-10-25T14:22:50.870Z
Martin B.
<p>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.</p>

<p><strong>Atomic Snapshot Object:</strong></p>

<p>In the paper <a href="http://dl.acm.org/citation.cfm?id=153724.153741" rel="nofollow">"Atomic Snapshots of Shared Memory"</a>, the authors consider atomic snapshot objects —— shared objects partitioned into segments. For the <strong>single-writer atomic snapshot object</strong>, each segment belongs to a different processor and is written separately, but all segments can be read at once by any processor. </p>

<blockquote>
  <p>The sequence specification of an atomic snapshot object provides two kinds of operations for each user $i, 0 \le i \le n-1$:</p>
  
  <ul>
  <li>A $scan_i$ invocation whose response is $return_i(V)$, where $V$ is an $n$-element vector called a <em>view</em> with a value for each segment, and</li>
  <li>An $update_i(d)$ invocation whose response is $ack_i$, where $d$ is the data to be written to $p_i's$ segment.</li>
  </ul>
  
  <p>A sequence of $scan$ and $update$ operations satisfies the <em>atomic snapshot semantics</em> 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$.</p>
</blockquote>

<p><strong>$K$-Atomic Object:</strong></p>

<p>In the paper <a href="http://www.cs.utexas.edu/~lorenzo/papers/disc05.pdf" rel="nofollow">On the Availability of Non-strict Quorum Systems</a>, $K$-atomic object is introduced. Different from the classical <strong>atomic object</strong> (see <a href="http://www.cse.huji.ac.il/course/2004/dist/p124-attiya.pdf" rel="nofollow">Sharing Memory Robustly in Message-Passing Systems</a>), in a system with $K$-atomic semantics,</p>

<blockquote>
  <p>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 <em>one of the values written by the last $K$</em> preceding writes in the order.</p>
</blockquote>

<p><strong>Problem 1: How to Define $K$-Atomic Snapshot Object?</strong></p>

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

<p>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?</p>

<p><em>One possible trial is to relax the timeliness of the snapshot:</em></p>

<blockquote>
  <p>A sequence of $scan$ and $update$ operations satisfies the <em>$K$-atomic snapshot semantics</em> means that, for each $V$ returned by a $scan$ operation, </p>
  
  <ul>
  <li><p>$V[i]$ equals one of the values written by the last $K$ preceding $update_{i}$s, for all $i$, and</p></li>
  <li><p>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$.</p></li>
  </ul>
</blockquote>

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

<p>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). </p>

<reference-request><dc.distributed-comp>
How to Define and Implement (Single-Writer) K-Atomic Snapshot Object?
hengxin
# How to Define and Implement (Single-Writer) K-Atomic Snapshot Object?

(Asked by: username_0 on 2013-09-20)

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"](http://dl.acm.org/citation.cfm?id=153724.153741), 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](http://www.cs.utexas.edu/~lorenzo/papers/disc05.pdf), $K$-atomic object is introduced. Different from the classical **atomic object** (see [Sharing Memory Robustly in Message-Passing Systems](http://www.cse.huji.ac.il/course/2004/dist/p124-attiya.pdf)), 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).

**Tags:** reference-request, dc.distributed-comp


---

## 1 answers

### Answer by username_1 on 2013-10-24. Score: 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.

> **Comments:**
> **username_0**: Regarding **Comment 1:** it is $\exists time : \forall i$. Regarding **Comment 2:** I agree with you that there is a possible definition in which no a time point when the memory actually had the value returned by $scan$ exists. Actually, [ZooKeeper](https://www.usenix.org/legacy/event/usenix10/tech/full_papers/Hunt.pdf) implements it and calls it _fuzzy snapshot_. However, theoretically, I am more interested in the definition which requires such points. AndI think both its computational power and implementations will be a challenge.  
> **username_0**: **Regarding general comment:** Of course, we can always implement (1-)atomic snapshot objects. However, maybe weaker versions are enough sometimes (e.g., as checkpoints for recovery). If we can implement $K-$atomic snapshot objects more efficiently, it is maybe useful. As for its computational power, can we relate it to $K-$mutual exclusion or $K-$set agreement (just my guess)? What do you think of it?  

---

