11institutetext: University of Tokyo
11email<EMAIL_ADDRESS>

# Operation-based Collaborative Data Sharing
for Distributed Systems

Masato Takeichi

###### Abstract

Collaborative Data Sharing raises a fundamental issue in distributed systems.
Several strategies have been proposed for making shared data consistent
between peers in such a way that the shared part of their local data become
equal.

Most of the proposals rely on state-based semantics. But this suffers from a
lack of descriptiveness in conflict-free features of synchronization required
for flexible network connections. Recent applications tend to use non-
permanent connection with mobile devices or allow temporary breakaways from
the system, for example.

To settle ourselves in conflict-free data sharing, we propose a novel scheme
Operation-based Collaborative Data Sharing that enables conflict-free
strategies for synchronization based on operational semantics.

##  1 Introduction

Each site, or peer of distributed systems has its exclusive property of the
contents and the policy for data sharing. For collaborative work between
peers, the peer expects partner peers to receive some of its data and asks
them for returning the updated data, or it asks partner peers to provide their
data for use with its local data.

This kind of data sharing is common in our real-world systems. Although data
sharing without updates is simple, collaborative data sharing with the update
propagation of shared data poses significant problems due to concurrent
updates of different instances of the same data. Which updates should be
allowed or how the update should be propagated to all the related peers are
the typical issues to be solved.

We have been discussing “What should be shared” in collaborative data sharing,
but not so much talking about “How should be shared”.

Concerning the “what”, a seminal work on Collaborative Data Sharing [8, 9]
brought several issues upon the specification of data to be shared. An
approach based on the view-updating technique with Bidirectional
Transformation [3, 2, 4, 5, 6] has been proved promissing. Among others, the
Dejima 1.0 architecture [7, 1] and the BCDS Agent [11] based on Bidirectional
Transformation reveal the effectiveness of using bidirectional transformation
for peers to control the accessibility of local data.

The basic scheme of these ideas is based on state-based semantics. That is,
data to be shared is compared with and moved to and from between peers.
Although this is straightforward in a sense, there may be several problems;
the size of messages for data exchange tends to grow, and possible conflicts
occur due to concurrent updates.

Looking from the other side, how to share data between peers is very similar
to how to synchronize distributed replicas to be the same. They are almost
equivalent except original intentions. And our problem to be solved is how to
synchronize distributed replicas in serverless distributed systems.

We have various kind of Conflict-free Replicated Data Types (CRDTs) [10]. The
CRDT approach restricts available operations acted on replicated data; the
Grow-Only-Set (G-Set) CRDT allows only the insertion operation on the set
data, for example. Concerning this, based on operational semantics, we propose
another schema for conflict-free data sharing using effectful operations that
enables us to insert and delete elements as we like [12].

In this paper, we will explore a novel scheme for collaborative data sharing
based on operational approach. The semantics of collaborative data sharing is
redefined using operations performed on peer’s local data. And as a natural
course, operations are exchanged each other for making effective data sharing
between peers.

Our Operation-based Collaborative Data Sharing (OCDS) can solve the problem
concerning possible conflicts between concurrent operations by conflict-free
synchronization for eventual consistency. And this accepts more operations
than CRDTs. It is the most remarkable feature of our OCDS compared with CRDTs.

##  2 Operations and Transformations in Data Sharing

The Dejima architecture mentioned in the previous section configures peers
with local data called Base Table and several additional Dejima Tables. The
shared data is located both in the Dejima Tables in peers $P$ and $Q$ as
illustrated in Fig.1. Bidirectional Transformation is employed to convert data
between the Base Table and the Dejima Table. It controls what to provide and
what to accept for data sharing.

Figure 1: Dejima Architecture for Collaborative Data Sharing

As described above, the Dejima architecture relies on state-based semantics.

We will give another definition of collaborative data sharing based on
operations on the local data. We assume that the configuration of peers is the
same as the Dejima architecture without the Dejima Table which corresponds to
the state of shared data.

#### Updating Operation

Peer $P$ has local data $D_{P}$ of (structured) type $\mathcal{D}_{P}$ with
operations on $\mathcal{D}_{P}$. The operation takes postfix form
$\odot_{P}p::\mathcal{D}_{P}\rightarrow\mathcal{D}_{P}$ where
$p\in{\cup_{D_{P}\in\mathcal{D_{P}}}}D_{P}$, which maps $D_{P}$ to
$D_{P}\odot_{P}p\in\mathcal{D}_{P}$, i.e., $D_{P}\mapsto D_{P}\odot_{P}p$.

From operational point of view, “$\odot_{P}p$ updates $D_{P}$ into
$D_{P}\odot_{P}p$”. Here, $p$ is not necessarily a single element, but may be
composed of several elements in ${\cup_{D_{P}\in\mathcal{D_{P}}}}D_{P}$. But,
for simplicity, we write them as a single $p$.

Operation $\odot_{P}p$ is derived from operator $\odot_{P}$ in $P$ indexed by
$p$. Operator $\odot_{P}$ stands for a generic symbol for $\oplus$, $\ominus$,
$\otimes$, $\oslash$, etc. For convenience, we use a postfix identity
operation “$!$” which does not change $D_{P}$, i.e., $D_{P}!=D_{P}$ for any
$D_{P}\in\mathcal{D}_{P}$.

#### Transformation Function

In addition to these operations, transformation functions $\langle
get_{P}^{q},put_{P}^{q}\rangle$, where
$get_{P}^{q}::\mathcal{D}_{P}\rightarrow\mathcal{D}$ and
$put_{P}^{q}::\mathcal{D}\rightarrow\mathcal{D}_{P}$ for some $\mathcal{D}$.

With a reservation, $put_{P}^{q}$ may use $\mathcal{D}_{P}$ along with
$\mathcal{D}$ as
$put_{P}^{q}::\mathcal{D}_{P}\times\mathcal{D}\rightarrow\mathcal{D}_{P}$.
This will be clear shortly with the reason why $\mathcal{D}_{P}$ appears in
the domain.

Same for the partner peer $Q$ with $\mathcal{D}_{Q}$ and $\langle
get_{Q}^{p},put_{Q}^{p}\rangle$, and $\mathcal{D}$ appeared in definitions in
$Q$ is common to $\mathcal{D}$ in $P$. Thus, $\mathcal{D}$ “combines” $P$ and
$Q$ as a connector for data exchange.

Suffixes for identifying the peer, e.g., $P$ in $\mathcal{D}_{P}$, $D_{P}$,
$\odot_{P}$, … are omitted when they are clear from the context.

#### Properties of Transformation Functions

Given data $D_{P}\in\mathcal{D}_{P}$ in $P$, $get_{P}^{q}(D_{P})$ gives some
$D\in\mathcal{D}$. And then, $Q$ gets share with data
$D_{Q}=put_{Q}^{p}(D)\in\mathcal{D}_{Q}$ which corresponds to $D_{P}$ in $P$.
And reciprocally, $P$ shares
$D_{P}^{\prime}=put_{P}^{q}(D^{\prime})=put_{P}^{q}(get_{Q}^{p}(D_{Q}^{\prime}))\in\mathcal{D}_{P}$
which corresponds to $D_{Q}^{\prime}$ in $Q$.

Intuitively, we may understand that part of $D_{P}$ and part of $D_{Q}$ are
shared each other.

If it happened to be $D=D^{\prime}$, it is natural to assume that
$D_{P}=D_{P}^{\prime}$ and $D_{Q}=D_{Q}^{\prime}$ hold with the above
equalities, so

$(put_{P}^{q}\cdot get_{Q}^{p})\cdot(put_{Q}^{p}\cdot
get_{P}^{q})=(put_{Q}^{p}\cdot get_{P}^{q})\cdot(put_{P}^{q}\cdot
get_{Q}^{p})=id$

hold. Then, what should we require for $get$ and $put$ in each peer?

Considering that $\langle get_{P}^{q},put_{P}^{q}\rangle$ and $\langle
get_{Q}^{p},put_{Q}^{p}\rangle$ are prepared independently in $P$ and $Q$, it
is reasonable to ask for

$\begin{split}put_{P}^{q}\cdot get_{P}^{q}&=get_{P}^{q}\cdot put_{P}^{q}=id\\\
put_{Q}^{p}\cdot get_{Q}^{p}&=get_{Q}^{p}\cdot put_{Q}^{p}=id\end{split}$

This is what we call the “Round-tripping” property of well-behaved
bidirectional transformation. And we require our $get$ and $put$ to satisfy
this property.

To define well-behaved bidirectional transformation $\langle
get_{P}^{q},put_{P}^{q}\rangle$, taking $\mathcal{D}_{P}$ along with
$\mathcal{D}$ as the domain of $put_{P}^{q}$ is of a great help to define
well-behaved transformation. From this reason, we sometimes define it as
$put_{P}^{q}::\mathcal{D}_{P}\times\mathcal{D}\rightarrow\mathcal{D}_{P}$.

From our operational viewpoint, this $put_{P}^{q}$ updates the current
instance $D_{P}$ of mutable data $\mathcal{D}_{P}$ with $D\in\mathcal{D}$ to
produce a new instance $D_{P}^{\prime}\in\mathcal{D}_{P}$. This is natural and
reasonable in that we may use the current data when updating mutable data.

##  3 Operation-based Collaborative Data Sharing

Local operation $\odot_{P}p$ causes an effect on elements of structured data
$D_{P}$ at a time, and therefore $D_{P}\odot_{P}p$ is a new instance
$D_{P}^{\prime}\in\mathcal{D}_{P}$ which is almost the same as $D_{P}$ except
for some different elements. A simple example of $\mathcal{D}_{P}$ is the set
with standard operations “insert an element $p$” (written as $\cup\\{p\\}$)
and “delete an element $p$”($\setminus\\{p\\}$).

As for collaborative data sharing between $P$ and $Q$, a straightforward
method for synchronization would be to exchange $D_{P}$ and $D_{Q}$ through
$D$ with transformation by $get$s and $put$s at the gateways of $P$ and $Q$.
This approach is called “state-based” because the state of the data is wholly
concerned in discussion.

Although the state-based approach to collaborative data sharing is most
common, it is not suitable for conflict-free strategies that aim to do
something gradually in $P$ and $Q$ for the shared part of $D_{P}$ and the part
of $D_{Q}$ to arrive at the same state eventually. The conflict-free approach
liberates us from the necessity of global locks for exclusive access to the
whole distributed data to avoid conflicts between concurrent updates. This is
particularly useful in distributed systems with no coordination by any peers
such as P2P-configured or composed of highly independent peers.

While the Conflict-free Replicated Data Type (CRDT) restricts operations so
that the data in each peer can be easily merged, our conflict-free approach
allows a wider class of operations that are common to general data structures.
Recently, a novel scheme for Conflict-free Collaborative Set Sharing [12] is
proposed using operations performed so far instead of directly merging the
current data. Although this concentrates on the set data, it can be extended
to our data sharing where transformations lie between peers’ local data.

###  3.1 Homomorphic Data Structures for Data Sharing

If $D_{Q}=put_{Q}^{p}(get_{P}^{q}(D_{P}))$ and
$D_{P}=put_{P}^{q}(get_{Q}^{p}(D_{Q}))$ hold, we say that “$D_{P}$ and $D_{Q}$
are consistent” and write this as $D_{P}\sim D_{Q}$. In other words,
consistent $D_{P}$ and $D_{Q}$ have corresponding parts which are shared each
other through intermediate data $D$ between them.

Assuming that $D_{P}\sim D_{Q}$, then what happens when operation $\odot_{P}p$
is performed on $D_{P}$ to produce $D_{P}\odot_{P}p$?

  * •

If $get_{P}^{q}(D_{P}\odot_{P}p)$ gives some $D^{\prime}$ which is to be
transformed next by $put_{Q}^{p}$, and

    * –

If $put_{Q}^{p}(D^{\prime})$ gives some $D_{Q}^{\prime}\in\mathcal{D}_{Q}$,
then $D_{P}\odot_{P}p\sim D_{Q}^{\prime}$.

    * –

Otherwise, $D_{P}\odot_{P}p$ has no corresponding instance in
$\mathcal{D}_{Q}$.

  * •

Otherwise, $D_{P}\odot_{P}p$ has no corresponding instance in
$\mathcal{D}_{Q}$.

Since $\odot_{P}p$ changes some elements of $D_{P}$, we hope that $D^{\prime}$
and $D_{Q}^{\prime}$ also change some element as $D^{\prime}=D\odot x$ and
$D_{Q}^{\prime}=D_{Q}\odot_{Q}q$ with $\odot x$ and $\odot_{Q}q$.

In most of our data sharing applications, $D_{P}$, $D_{Q}$ and intermediate
data $D$ are homomorphic each other in that the above conditions are
satisfied.

In this respect, our transformation functions $get$ and $put$ partly provide
homomorphism. The simplest example would be the case where all the related
data structures are sets or SQL tables, etc. In general, these are not
necessarily the same but are homomorphic. And we need more about homomorphism
on operations for our operation-based data sharing.

#### Homomorphic Data Structures with Operations

Data type $\langle\mathcal{A},\circledcirc_{A}\rangle$ is closed with respect
to operations $\circledcirc_{A}a$ for any $a\in\cup_{A\in\mathcal{A}}A$, where
operator symbol
$\circledcirc_{A}::(\mathcal{A},\cup_{A\in\mathcal{A}}A)\rightarrow\mathcal{A}$
represents any operators in $\mathcal{A}$. We simply write here
$\circledcirc_{A}$ for the set of operators in $\mathcal{A}$ and use the same
symbol for one of them as a generic operator in an overloaded manner.

The operation $\circledcirc_{A}a::\mathcal{A}\rightarrow\mathcal{A}$ is
postfixed to the operand $A\in\mathcal{A}$ to produces
$A^{\prime}=A\circledcirc_{A}a\in\mathcal{A}$.

This models the mutable state data $A$ with operations $\circledcirc_{A}a$ on
$A$ using some element $a$.

#### Definition of Homomorphic Data Types

Data types $\langle\mathcal{A},\circledcirc_{A}\rangle$ and
$\langle\mathcal{B},\circledcirc_{B}\rangle$ are homomorphic if there exist
$h::\mathcal{A}\rightarrow\mathcal{B}$ and overloaded
$h::\circledcirc_{A}\rightarrow\circledcirc_{B}$ satisfying

$\begin{split}&\forall A\in\mathcal{A}.\exists B\in\mathcal{B}.B=h(A)\\\
&\forall A\in\mathcal{A}.\forall a\in\cup_{A\in\mathcal{A}}A.\exists
B\in\mathcal{B}.\exists
b\in\cup_{B\in\mathcal{B}}.B\circledcirc_{B}b=h(A\circledcirc_{A}a)\end{split}$

We assume that every data type $\langle\mathcal{A},\circledcirc_{A}\rangle$
has an identity operation “$!$” which does not affect the state of data. That
is, for any $A\in\mathcal{A}$, $A!=A$ holds.

In short, for operation-based collaboration, we require operations to exchange
between homomorphic data types so that operation on a peer corresponds to
operation on the partner peer.

#### Examples of Homomorphic Data Types

Previous works on state-based data sharing with transformation [7, 1, 11]
exclusively deal with SQL databases as local data. Specifically, if the
intermediate data $D$ is defined as the view of the SQL table $D_{P}$ of the
local data, it is obvious that $D_{P}$ and $D$ are homomorphic because $D$ is
produced by selection and projection of $D_{P}$. The Dejima architecture
allows so-called SPJU (Select-Project-Join-Union) queries by the SQL’s SELECT-
FROM-WHERE-UNION construct for the view. But, since it is not clear what
operations are permitted on (multiple) SQL tables of $D_{P}$, we need more to
work on making sure that $D_{P}$ and $D$ are homomorphic. We leave this for
the future.

As a demonstration of the independence of implementation of the local data
$D_{P}$ from the intermediate data $D$ of our operation-based data sharing,
consider the case that $D$ is a set, i.e., no duplicates in aggregation, and
$D_{P}$ implements set by the binary search tree. In this case, we easily give
a homomorphism mapping from $D_{P}$ to $D$. Or, it should be grounded in the
data abstraction mechanism.

As for the relationship of homomorphic data types with state machines, see the
Appendix.

###  3.2 Transformation of Operations

For homomorphic data structures $\langle\mathcal{D}_{P},\odot_{P}\rangle$,
$\langle\mathcal{D},\odot\rangle$ and
$\langle\mathcal{D}_{Q},\odot_{Q}\rangle$, operations are transformed
according to the hompmorphisms by $get$ and $put$. We write

> $\odot_{P}{}_{P}^{q}\\!{\rightarrowtail}\odot x$, if
> $get_{P}^{q}(D_{P}\odot_{P}p)$ gives $D\odot x$.
> $\odot x~{}{\looparrowright}_{Q}^{p}\odot_{Q}q$, if $put_{Q}^{p}(D\odot x)$
> gives $D_{Q}\odot_{Q}q$

Our Operation-based Collaborative Data Sharing wholly sends and receives
operations instead of data as shown in the diagram of Fig.2.

Figure 2: Operation-based Collaborative Data Sharing

In this way, peers communicate updating operations to and from each other with
necessary transformation at the gateway of the peer.

##  4 Architecture for Collaborative Data Sharing

Peers of our Collaborative Data Sharing run concurrently and they transmit
their updates asynchronously to and from each other. Thus, the payload of the
communication message between peers is the updating operation from a peer to
its partner peer.

The peer as the client sends local operations to the partner peers, and as the
server receives remote operations from the partners and then perform necessary
operations to reflect them on the local data.

In these processes, each peer works as follows. Peer $P$ asynchronously
receives local operations from the user and remote operations from the partner
peers. These operations are to be performed on $D_{P}$ and are stored in the
queue for serialized access to $D_{P}$.

So far, we explained our scheme solely with peers $P$ and $Q$. But, in
general, each peer $P$ has multiple peers connected in the system. For $P$ to
do with all the partmer peers, we need to clarify how $P$ should do.

In peer $P$, every update on data $D_{P}$ is propagated to all the partner
peers $k=\cdots,Q,\cdots$ through the outgoing communication ports prepared
for each peer $k$ after it is transformed by ${}_{P}^{k}\\!{\rightarrowtail}$.
And remote operations from peers are received asynchronously from the partner
peers $K=\cdots,Q,\cdots$ through the incoming ports each prepared for the
peer $k$ and transformed by ${\looparrowright}_{P}^{k}$.

As the local and remote operations arrive asynchronously, the peer needs to
provide queues for them to perform the operations on the local data.

In addition to this, we follow the scheme of Conflict-free Collaborative Set
Sharing described in [12] for conflict-free synchronization.

We call the implementation of the peer as described above by the name “OCDS
Agent”.

The OCDS Agent is developed to achieve conflict-free synchronization of the
local data using internal queues for serialization of asynchronous access to
the local data and asynchronous transmission of operations as illustrated in
Fig.3.

Figure 3: OCDS Agent for Operation-based Collaborative Data Sharing

##  5 An Example of Operation-based Collaborative Data Sharing

#### Sharing Double and Triple Numbers

Let $D_{P}$ be a set of integers with operations “insert an element $p$”
($\cup\\{p\\}$) and “delete an element $p$”($\setminus\\{p\\}$).

Bidirectional transformation defied in $P$ is

$\begin{split}get_{P}^{p}(D_{P})&=\\{p~{}|~{}p\%2=0,~{}p\in D_{P}\\}\\\
put_{P}^{q}(D_{P},D)&=D_{P}\setminus
get_{P}^{q}(D_{P})\cup\\{x~{}|~{}x\%2=0,~{}x\in D\\}\end{split}$

where $\%$ represents the modulo operation.

Functions $get_{P}^{q}$ and $put_{P}^{q}$ define the mapping for view-updating
of the state-based approach; $get_{P}^{q}$ produces the view
$D=get_{P}^{q}(D_{P})$, and $put_{P}^{q}$ replects the update $D^{\prime}$ of
$D$ onto the source as $D_{P}^{\prime}=put_{P}^{q}(D_{P},D)$. We can see that
this bidirectional transformation $\langle get_{P}^{q},put_{P}^{q}\rangle$
satisfies the round-tripping property and so is well-behaved.

Similarly, defined in $Q$:

$\begin{split}get_{Q}^{p}(D_{Q})&=\\{q~{}|~{}q\%3=0,~{}q\in D_{Q}\\}\\\
put_{Q}^{p}(D_{Q},D)&=D_{P}\setminus
get_{Q}^{p}(D_{Q})\cup\\{x~{}|~{}x\%3=0,~{}x\in D\\}.\end{split}$

Then, we use these for data sharing in a way that the intermediate data $D$
represents shared data consisting elements in both of $get_{P}^{q}(D_{P})$ and
$get_{Q}^{p}(D_{Q})$, i.e., $D=get_{P}^{q}(D_{P})\cap get_{Q}^{p}(D_{Q})$. In
brief, $D$ contains sextuple numbers, i.e., numbers divisible by 6, common to
$D_{P}$ and $D_{Q}$.

We can confirm by the state-based semantics that local updates in $P$ and $Q$
are faithfully reflected in both $D_{P}$ and $D_{Q}$ through the Dejima $D$ if
this condition holds.

Now, we are going to our operation-based sharing.

Recall that $get_{P}^{q}$ tells us that $P$ is willing to share double numbers
with $Q$, and that $get_{Q}^{p}$ tells us that $Q$ is willing to share triple
numbers with $P$. However, the $put$ functions tell us that $P$ will accept
only double numbers, and $Q$ will accept only triple numbers from the common
intermediate data $D$.

A short story is here:

  1. 1.

Start from $D_{P}=\\{1,2,3,4\\}$ and $D_{Q}=\\{2,3,4,9\\}$. They are
consistent, i.e., $D_{P}\sim D_{Q}$ since $D=\\{\\}$.

  2. 2.

Network connection fails.

  3. 3.

Concurrently, $P$ does $\cup\\{6\\}$ and $Q$ does $\setminus\\{4\\}$.

  4. 4.

Connection restored, and synchronization processes start in $P$ and $Q$
independently.

Then, what happens in synchronization processes?

These operations are in fact effectful111 The concept of the “effectful”
operation is described in [12] in that $\cup\\{6\\}$ is applied to $D_{P}$
which does not contain $6$, and $\setminus\\{4\\}$ is applied to $D_{Q}$ which
does contain $4$.

In Step 3, $P$’s local data becomes
$D_{P}^{\prime}=D_{P}\cup\\{6\\}=\\{1,2,3,4,6\\}$, and $Q$’s local data
becomes $D_{Q}^{\prime}=D_{Q}\setminus\\{4\\}=\\{2,3,9\\}$.

Synchronization proceeds as

  * •

Since
$\cup\\{6\\}{}_{P}^{q}\\!{\rightarrowtail}\cup\\{6\\}{\looparrowright}_{Q}^{p}$,
$6$ is added to $D_{Q}^{\prime}$ to produce
$D_{Q}^{\prime\prime}=D_{Q}^{\prime}\cup\\{6\\}=\\{2,3,6,9\\}$.

  * •

On the other direction, since $\setminus\\{4\\}$ in $Q$ cannot be passed to
${}_{Q}^{p}\\!{\rightarrowtail}$ because $get_{Q}^{p}$ rejects $4$, this
operation does not arrive at $P$.

Thus, these synchronization processes concurrently done in $P$ and $Q$ lead
$P$’s data and $Q$’s data to the consistent state, i.e., $D_{P}^{\prime}\sim
D_{Q}^{\prime\prime}$ with $D=\\{6\\}$.

Another story is here: In Step 3 above, what happens if “$Q$ does
$\setminus\\{6\\}$” instead of “$Q$ does $\setminus\\{4\\}$”?

Note that these operations are not effectful because $\setminus\\{6\\}$ here
is applied to $D_{Q}$ which does not contain $6$. During the period of network
failure, $P$’s local data becomes
$D_{P}^{\prime}=D_{P}\cup\\{6\\}=\\{1,2,3,4,6\\}$ as before, and $Q$’s local
data remains at it has been because
$D_{Q}^{\prime}=D_{Q}\setminus\\{6\\}=\\{2,3,4,9\\}$.

Synchronization proceeds as follows after the network connection is restored.

  * •

$\cup\\{6\\}{}_{P}^{q}\\!{\rightarrowtail}\cup\\{6\\}{\looparrowright}_{Q}^{p}$
causes changes $D_{Q}^{\prime\prime}=D_{Q}^{\prime}\cup\\{6\\}=\\{2,3,6,9\\}$
as the previous case.

  * •

And since
$\setminus\\{6\\}{}_{Q}^{p}\\!{\rightarrowtail}\setminus\\{6\\}{\looparrowright}_{P}^{q}\setminus\\{6\\}$,
$P$ may produces a new state
$D_{P}^{\prime\prime}=D_{P}^{\prime}\setminus\\{6\\}=\\{1,2,3,4\\}$.

If the synchronization in $P$ proceeds as above, $P$ loses $6$ which was added
in Step 3, while it is added to $Q$’s local data by $Q$’s synchronization.
This breaks the consistency of $D_{P}^{\prime\prime}$ and $D_{Q}^{\prime}$.

From these examples, we observe that the effectful set operations in
concurrent updates is essential for conflict-free synchronization. They
effectively avoid insertion/deletion conflicts in synchronization. This is an
extension of the scheme for data sharing described in [12]. Here, we used
transformations $get$ and $put$ at the gateways of the peers.

##  6 Remarks

We can employ our OCDS Agent for configuring serverless distributed systems
with ensuring eventual consistency of peers’ local data.

We may consider this as an alternative scheme for the Dejima style data
sharing [7] that has been implemented to ensure the global strong consistency
by locking on the way during the update propagation. Our conflict-free
approach allows peers to leave and join at any time and can afford to the
network failure and restoration.

A remarkable feature of our OCDS is that it enables us to control the data;
what to provide and what to accept for sharing with other peers. This
contrasts clearly with other conflict-free data sharing or data
synchronization of replicated data such as CRDTs.

## References

  * [1] Y. Asano, Z. Hu, Y. Ishihara, M. Onizuka, M. Takeichi, and M. Yoshikawa.  Data integration models and architectures for service alliances.  In Proceedings of the 4th Workshop on Software Foundations for Data Interoperability (SFDI2020), CCIS1281, pages 152–164. Springer, 2020.
  * [2] A. Bohannon, J. N. Foster, B. C. Pierce, A. Pilkiewicz, and A. Schmitt.  Boomerang: Resourceful lenses for string data.  In POPL, pages 407–419, 2008.
  * [3] J. N. Foster, M. B. Greenwald, J. T. Moore, B. C. Pierce, and A. Schmitt.  Combinators for bidirectional tree transformations: A linguistic approach to the view-update problem.  ACM Transactions on Programming Languages and Systems, 29(3):17, 2007.
  * [4] S. Hidaka, Z. Hu, K. Inaba, H. Kato, K. Matsuda, and K. Nakano.  Bidirectionalizing graph transformations.  In ICFP, pages 205–216, 2010.
  * [5] Z. Hu, S.-C. Mu, and M. Takeichi.  A programmable editor for developing structured documents based on bidirectional transformations.  Higher-Order and Symbolic Computation, 21(1-2):89–118, 2008.
  * [6] Z. Hu, A. Schürr, P. Stevens, and J. F. Terwilliger.  Dagstuhl seminar on bidirectional transformations (BX).  SIGMOD Record, 40(1):35–39, 2011.
  * [7] Y. Ishihara, H. Kato, K. Nakano, M. Onizuka, and Y. Sasaki.  Toward BX-based architecture for controlling and sharing distributed data.  In 2019 IEEE International Conference on Big Data and Smart Computing (BigComp), pages 1–5, 2019.
  * [8] Z. Ives, N. Khandelwal, A. Kapur, and M. Cakir.  ORCHESTRA: Rapid, collaborative sharing of dynamic data.  In CIDR, pages 107–118, 2005.
  * [9] G. Karvounarakis, T. J. Green, Z. G. Ives, and V. l Tannen.  Collaborative data sharing via update exchange and provenance.  ACM Transactions on Database Systems, 38(3):19:1–19:42, 2013.
  * [10] M. Shapiro, N. Preguiça, C. Baquero, and M. Zawirski.  Conflict-free replicated data types.  In 13th International Conference on Stabilization, Safety, and Security of Distributed Systems, SSS 2011, pages 386–400. Springer LNCS volume 6976, Oct. 2011.
  * [11] M. Takeichi.  BCDS Agent: An architecture for bidirectional collaborative data sharing.  In Computer Software, Japan Society for Software Science and Technology, Vol.38, No.3., pages 41–57, 2021.  Also available at https://www.jstage.jst.go.jp/article/jssst/38/3/38_3_41/_pdf/-char/ja.
  * [12] M. Takeichi.  Conflict-free collaborative set sharing for distributed systems.  2021\.  Technical Report available at http://takeichimasato.net/blog/wp-content/uploads/2021/11/TR-CCSS.pdf.

Appendix

#### Example of Homomorphic States

Let $\langle\mathcal{A},\circledcirc_{A}\rangle$ show the state of the door at
the entrance and $\langle\mathcal{B},\circledcirc_{B}\rangle$ show the state
of the electric light of the entrance hall.

> $\mathcal{A}=\\{\\{{\sf DoorOpen}\\},\\{{\sf DoorClosed}\\}\\}$
> $\circledcirc_{A}:$ $\circleddash$ for Open, $\otimes$ for Close,
> $\circledast$ for RingBell.

> $\mathcal{B}=\\{\\{{\sf LightLit}\\},\\{{\sf LightDim}\\}\\}$
> $\circledcirc_{B}:$ $\oplus$ for On, $\ominus$ for Off.

See the transitions in Fig.4. Note that every operator $\circledcirc$ takes an
operand after it to validate application, e.g., RingBell operation
$\circledast$ is valid only if the current state is $\sf DoorClosed$.

Figure 4: Collaborative Working Door and Light

We can define the homomorphic mapping $h$ from
$\langle\mathcal{A},\circledcirc_{A}\rangle$ to
$\langle\mathcal{B},\circledcirc_{B}\rangle$.

  * •

For $\mathcal{A}$ to $\mathcal{B}$,

$h(\\{{\sf DoorOpen}\\})=\\{{\sf LightLit}\\},h(\\{{\sf
DoorClosed}\\})=\\{{\sf LightDim}\\}$

  * •

For $\circledcirc_{A}$ to $\circledcirc_{B}$,

$\begin{split}&h(\circleddash\\{{\sf DoorClosed}\\})=\ominus\\{{\sf
LightLit}\\},h(\otimes\\{{\sf DoorOpen}\\})=\oplus\\{{\sf LightDim}\\},\\\
&h(\circledast\\{{\sf DoorClosed}\\})=!\end{split}$

Thus, the door and the light work together. Along with the homomorphism for
the reverse direction gives us the collaborative updates of the states of the
door and the light.