###### Abstract

Data reconciliation in general, and filesystem synchronization in particular,
lacks rigorous theoretical foundation. This paper presents, for the first
time, a complete analysis of synchronization for two replicas of a theoretical
filesystem. Synchronization has two main stages: identifying the conflicts,
and resolving them. All existing (both theoretical and practical)
synchronizers are _operation-based:_ they define, using some rationale or
heuristics, how conflicts are to be resolved without considering the effect of
the resolution on subsequent conflicts. Instead, our approach is _declaration-
based:_ we define what constitutes the resolution of all conflicts, and for
each possible scenario we prove the existence of sequences of
operations/commands which convert the replicas into a common synchronized
state. These sequences consist of operations rolling back some local changes,
followed by operations performed on the other replica. The set of rolled-back
operations provides the user with clear and intuitive information on the
proposed changes, so she can easily decide whether to accept them or ask for
other alternatives. All possible synchronized states are described by
specifying a set of conflicts, a partial order on the conflicts describing the
order in which they need to be resolved, as well as the effect of each
decision on subsequent conflicts. Using this classification, the outcomes of
different conflict resolution policies can be investigated easily.

###### keywords:

data synchronization; conflict resolution, filesystem theory

1 1 0 https://doi.org/ Data Synchronization: A Complete Theoretical Solution
for Filesystems Data Synchronization: A Complete Theoretical Solution for
Filesystems Elod P. Csirmaz1,∗ and Laszlo Csirmaz2 Elod P. Csirmaz and Laszlo
Csirmaz Csirmaz, E. P; Csirmaz, L Correspondence<EMAIL_ADDRESS>08A02,
08A70, 68M07, 68P05

##  1 Introduction

This work is a comprehensive treatment of filesystem synchronization and
conflict resolution on a simple but powerful theoretical model of filesystems.
Synchronizing diverged copies of some data stored on a variety of devices and
locations is an important and ubiquitous task. The last two decades have seen
tremendous advancement, both theoretical and practical, in the closely related
fields of distributed data storage CRDT-overview ; CRDT-orig  and group
editors SJZ98 ; SE98 . This progress has been based on, and has expanded
significantly, two competing theoretical frameworks: Operational
Transformation (OT) and Conflict-free Replicated Data Types (CRDT). OT
appeared in the seminal work EG89  and was refined later in SE98 . The general
idea is that operations are enriched with the context in which they were
generated. Before applying them, they are _transformed_ depending on the
context of their origin and the context where they are to be applied. Main
applications are collaborative editors, the most notable example being Google
Docs DR10 . The core concept of CRDT is _commutativity_ , see CRDT-orig ;
CRDT-overview . Basic data types with special operators are devised so that
executing the operators in different orders yields the same results. Examples
are counters or sets with add and delete operators. The basic types are used
as building blocks in more complex applications such as collaborative editors
NIC16 , the commercial product Riak KLO10 , and others.

Both OT and CRDT have been successfully applied in a variety of
synchronization tasks NS16 ; TSR15 . Filesystem synchronization, however, fits
very poorly into these frameworks, mainly because it works under completely
different _modus operandi_ : constant, low latency communication in OT and
CRDT versus a single data exchange in filesystem synchronization; frequent
loose synchronization with eventual convergence requirement versus a single
but complete synchronization; small number of differences versus significant
structural differences accumulated during an extended time period; and so on.
Consequently, for a theoretical investigation of filesystem synchronization,
we follow a traditional framework instead, described in e.g. BP98  and
depicted in Figure 1 adapted from CC22 .

$\Phi$$\Phi$$\Phi$$\Phi_{1}$$\Phi_{2}$$\Psi$$\Psi$$\Psi$…… merged state …………
replicas ……update detectorupdate detectorreconciler
$\scriptstyle\alpha_{0}$updates$\scriptstyle\beta_{0}$updates$\scriptstyle\alpha_{1}$synchronization$\scriptstyle\beta_{1}$synchronization$\scriptstyle\alpha$$\scriptstyle\beta$
Figure 1: The synchronization process

Two identical replicas of the original filesystem $\Phi$ are updated
independently, yielding the diverged replicas $\Phi_{1}$ and $\Phi_{2}$. In
the state-based case the _update detector_ receives the original ($\Phi$) and
the current ($\Phi_{1}$ or $\Phi_{2}$) states, and generates the update
information $\alpha$ (or $\beta$) describing the differences between the
original filesystem and the replica. In the operation-based case the update
decoder has access to the performed operations $\alpha_{0}$ ($\beta_{0}$)
only. The _reconciler_ receives the information provided by the update
detectors and generates the synchronizing instructions $\alpha_{1}$ and
$\beta_{1}$, respectively. These instructions, applied to the replicas
$\Phi_{1}$ and $\Phi_{2}$, create the identical _merged state $\Psi$_.

In order to reach such a common synchronized state, existing theoretical and
practical filesystem synchronizers, such as IceCube ; MPV ; PV ; syncpal-
thesis ; TSR15 ; TTPDSH , apply some conflict-resolution strategy. They
identify all (or some) of the conflicts, then apply their strategy to the
conflicts one at a time. These algorithms are typically fixed and defined by
some rationale or heuristics, or dictated by the underlying technology. In
contrast, we _define what comprises a synchronized state._ Intuitively, it is
a maximal consistent merger of the replicas, meaning that no further changes
can be applied to the merged state from those that were applied to the
replicas during the update phase. Then we proceed to prove that every such
maximal state (and only these states) can be reached by resolving the
conflicts in some order.

In a meticulous survey of existing theoretical and practical filesystem
synchronizers syncpal-thesis  it has been observed that “resolving conflicts
is an open problem where […] most academic works present arbitrary resolution
methods that lack a rationale for their decisions” (page i), and that “a file
system can be affected by more than one conflict at once, which has not been
discussed in related academic works” (page 65). By presenting, for the first
time, a complete analysis of the synchronization process for two replicas of a
theoretical filesystem model, we fill these gaps.

##  2 Materials and Methods

Our filesystem model, defined in Section 3, is arguably simple, but it retains
all important structural properties of real filesystems. It is this simplicity
that allows us to exploit a rich and intriguing algebraic structure Csi16 ;
CC22  which eventually leads to the claimed theoretical results. In Section 7
we discuss some possible extensions of the filesystem model.

Depending on the data communicated by the replicas, synchronizers are
categorized as either _state-based_ or _operation-based_ syncpal-thesis ;
CRDT-overview . In state-based synchronization replicas send their current
versions of the filesystem, or merely the differences (called _diff_ s)
between the current states and the last known synchronized state AC08 .
Operation-based synchronizers transmit the complete log (or trace) of all
operations performed by the user IceCube . The synchronization method of this
paper is reminiscent of operation-based one, but can also be considered, with
similar overhead, to be state-based. A set of virtual filesystem operations
(commands) will be defined in Section 3. Each of these commands have a clear
and intuitive operational meaning, but are not necessarily available to the
end-user. The current state of the filesystem is described by a special –
called _canonical_ – sequence of virtual commands, which transforms the
original filesystem to the actual replica. The _update detector_ can generate
this canonical sequence from the operations performed by the user on the
replica (operation-based) as well as from the differences between the original
and final state (state-based). On Figure 1 these sequences correspond to the
information in $\alpha$ and $\beta$ passed to the reconciler.

Filesystem synchronization must resolve all conflicts between the replicas.
Conflict resolution, however, should be “intuitively correct,” i.e. discarding
all changes made by both replicas is not a viable alternative. The majority of
commercially or theoretically available synchronizers do not present a
rationale to explain their concrete conflict resolution approach syncpal-
thesis . Two notable exceptions are TSR15  and NS16  which describe high-level
consistency philosophies. In TSR15  the main principles are 1) _no lost
update:_ preserve all updates on all replicas because these updates are
equally valid; and 2) _no side effects:_ such as a merge where objects
unexpectedly disappear. While these principles intuitively make sense, it is
easy to see that neither could possibly be upheld for every conflict; even the
authors provide counterexamples. In NS16  the relevant consistency
requirements are worded as follows:

  * R1

_intention-confined effect:_ operations applied to the replicas by the
synchronizer must be based on operations generated by the end-user; and

  * R2

_aggressive effect preservation:_ the effect of compatible operations should
be preserved fully; and the effect of conflicting operations should be
preserved as much as possible.

These requirements are in fact variations of the OT consistency model, see for
example the notion of intention preservation in SE98 . (We note that the other
two OT principles – convergence and causality preservation – do not apply to
filesystem synchronizers.)

In agreement with R1 and R2 we _declare_ what a synchronized state is, rather
than present an algorithm which generates it. Our declaration can be outlined
as follows. Suppose that the two replicas $\Phi_{1}$ and $\Phi_{2}$ are
represented by the canonical sequences $\alpha$ and $\beta$, respectively,
that is, $\Phi_{1}=\alpha\Phi$ and $\Phi_{2}=\beta\Phi$, where $\alpha\Phi$ is
the result of applying the command sequence $\alpha$ to $\Phi$. The
_synchronized_ or _merged state $\Psi$_ is determined by the canonical
sequence $\mu$ as $\Psi=\mu\Phi$ such that

  * C0

$\mu$ is applicable to the original filesystem $\Phi$,

  * C1

every command in $\mu$ can be found either in $\alpha$, in $\beta$, or in
both, and

  * C2

$\mu$ is maximal, i.e. no canonical sequence adding more commands to $\mu$ can
satisfy both C0 and C1.

Condition C0 is the obvious requirement that the synchronizer must not cause
errors. Condition C1 ensures that the synchronization satisfies the
_intention-confined effect_ (no surprise changes in the merged filesystem)
requirement R1 as $\mu$ should consist only of commands which were supplied by
the replicas. The other consistency requirement R2 is guaranteed by C2 as
$\mu$ is maximal, therefore it preserves as much of the intention of the users
as possible. Note that this definition of a synchronized state is never
vacuous. There are only finitely many sequences which satisfy C0 and C1, and
there are at least two, namely $\alpha$ and $\beta$. Because of this, the
empty sequence (undoing all changes) will not satisfy C2 (assuming one of
$\alpha$ and $\beta$ is not empty), in line with our requirements.

The declaration-based synchronization is intuitively clear, easy to
understand, and does not use any predetermined conflict-resolving policy. An
operational characterization is proved in Theorem 5. The essence of this
theorem is that any merged filesystem $\Psi$ can be generated from the
replica, say $\Phi_{1}$, by

  * 1.

rolling back some of the commands in $\alpha$, followed by

  * 2.

applying some commands from the other sequence $\beta$,

and _vice versa_ for the other replica. The commands rolled back represent a
minimal set whose removal resolves all conflicts. These commands also give
users a clear understanding of the changes the synchronizer wants to perform
on their filesystem. They are also helpful when some of the rolled-back
commands should be introduced again after the merging (doing a redo of the
undo).

Turning to traditional conflict-based synchronization, Section 6 proves that
any declaration-based merged state, and only those states, can be the result
of a conflict-based synchronization algorithm. For each pair of canonical
sequences describing the replicas to be synchronized we define what the
conflicting command pairs are. Their resolution uses the winner/loser
paradigm: the winner command is accepted while the loser command is discarded.
It turns out that resolving a conflict may automatically resolve some of the
subsequent conflicts, but no new conflicts are created. Using this result the
outcomes of different conflict resolving policies can be investigated easily.
In particular, the _iterative approach_ syncpal-thesis  always works, which
applies all non-conflicting commands, resolves, in any way, the first conflict
(which might automatically resolve other existing conflicts), and iterates.

##  3 Definitions

This section defines the basic notation which will be used throughout the rest
of the paper. The exposition follows Csi16  and CC22  with some substantial
modifications. Some results from these papers are included without proof.

###  3.1 Namespace and filesystems

Our filesystem model is arguably simplistic, nevertheless it captures all
important aspects of real-word implementations. In spirit, it is a mixture of
_identity-_ and _path-based_ models syncpal-thesis ; TSR15 . Objects are
stored in nodes, which are uniquely identified by fixed and predetermined
_path_ s. The set of available nodes is fixed in advance, and no path
operations are considered. Filesystems are required to have the _tree-
property_ at all times: in a given filesystem along any branch starting from
any of the root nodes, there must be zero or more _directories_ , zero or one
_file_ , followed by _empty_ nodes. Our model does not support _links_ (but
see Section 7.4), thus the namespace – the set of available nodes or paths –
forms a collection of rooted trees. Filesystems are defined over and populate
this fixed namespace.

Formally, the _namespace_ is a set $\mathbb{N}$ endowed with the partial
function ${\uparrow}:\mathbb{N}\to\mathbb{N}$ returning the parent of every
non-root node (it is not defined on roots). If $n={\uparrow}m$ then $n$ is the
parent of $m$, and $m$ is a child of $n$. For two nodes $n,m\in\mathbb{N}$ we
say that _$n$ is above $m$_, or $n$ is an ancestor of $m$, and write $n\prec
m$ if $n={\uparrow}^{i}(m)$ for some $i\geq 1$. As usual, $n\preccurlyeq m$
means $n\prec m$ or $n=m$. As the parent function induces a tree-like
structure, $\preccurlyeq$ is a partial order. Two nodes $n,m\in\mathbb{N}$ are
_comparable_ if either $n\preccurlyeq m$ or $m\preccurlyeq n$, and they are
_uncomparable_ or _independent_ otherwise.

A _filesystem $\Phi$_ populates the nodes of the namespace with values. The
value stored at node $n\in\mathbb{N}$ is denoted by $\Phi(n)$. This value can
be $\mathbb{O}$ indicating that the node is _empty_ (no content, not to be
confused with the empty file); can be $\mathbb{D}$ indicating that the node is
a _directory_ ; otherwise it is a _file_ storing the complete content (which
could happen to be “no content”). We use $\mathbb{O}$, $\mathbb{D}$ and
$\mathbb{F}$ to denote the _type_ of the content corresponding to these
possibilities. While there is only one value of type $\mathbb{O}$ and one
value of type $\mathbb{D}$ (see Section 7.3 for a discussion on lifting this
limitation), there are many different file values of type $\mathbb{F}$
representing different file contents.

###  3.2 Internal filesystem commands

The synchronizer operates using a specially designed and highly symmetrical
set of _internal filesystem commands_. They each modify the filesystem at a
single node only, and contain additional information usually not thought of as
part of a command which allows them to be inverted, and makes them amenable to
algebraic manipulation. Inventing such a command set was one of the main
contributions of Csi16 .

The commands basically implement creating and deleting files and directories.
Modifying a part of a file only is not available as a command; whenever a file
is modified, the new content must be supplied in its entirety. Still, commands
issued by a real-life user or system can be easily transformed into the
internal commands; for example, the _move_ or _rename_ operation can be
modeled as a sequence of a _delete_ and a _create_.

The set of the internal commands is denoted by $\Omega$, and each command
$\sigma\in\Omega$ has three components, written as $\sigma=\langle
n,x,y\rangle$, as follows:

  * •

$n\in\mathbb{N}$ is the node on which the command acts,

  * •

$x$ is the content at node $n$ before the command is executed (precondition),
and

  * •

$y$ is the content at node $n$ after the command was executed.

Thus _rmdir_ $(n)$ corresponds to the internal command $\langle
n,\mathbb{D},\mathbb{O}\rangle$, which replaces the directory value at $n$ by
the empty value. The command $\langle n,\mathbb{O},\mathbb{D}\rangle$ creates
a directory at $n$, but only if the node $n$ has no content, i.e., there is no
directory or file at $n$ (a usual requirement for _mkdir_ $(n)$). For files
$\mathsf{f}_{1}$ and $\mathsf{f}_{2}\in\mathbb{F}$ the command $\langle
n,\mathsf{f}_{1},\mathsf{f}_{2}\rangle$ replaces $\mathsf{f}_{1}$ stored at
node $n$ by the new content $\mathsf{f}_{2}$. This latter command can be
considered to be an equivalent of _edit_ $(n,\mathsf{f}_{1},\mathsf{f}_{2})$.

Applying $\sigma\in\Omega$ to a filesystem $\Phi$ is written as the left
action $\sigma\Phi$. The command $\sigma=\langle n,x,y\rangle$ is _applicable_
to $\Phi$ if

  * •

$\Phi$ contains $x$ at the node $n$, that is, $\Phi(n)=x$, and

  * •

after changing the content at $n$ to $y$ the filesystem still has the tree
property.

If $\sigma$ is not applicable to $\Phi$ then we say that $\sigma$ _breaks_ the
filesystem, and write $\sigma\Phi=\bot$. If $\sigma$ does not break $\Phi$,
then $\sigma\Phi$ is the filesystem where every node has the same value as in
$\Phi$ except for the node $n$ where the new content is $y$. Command sequences
are applied from left to right, thus $(\sigma\alpha)\Phi=\alpha(\sigma\Phi)$.
The composition of sequences $\alpha$ and $\beta$ is written as $\alpha\beta$;
occasionally we write it as $\alpha\circ\beta$ to emphasize that $\beta$ is to
be executed after $\alpha$. A sequence breaks $\Phi$ if one of its commands is
not applicable. More formally, $\sigma\alpha$ breaks $\Phi$ if either $\sigma$
breaks $\Phi$, or $\alpha$ breaks $\sigma\Phi$.

Two additional commands will be used, which are denoted by $\epsilon$ and
$\lambda$, respectively. In practice they do not occur, and cannot be elements
of command sequences, but are useful in algebraic derivations. The command
$\epsilon$ breaks every filesystem, while $\lambda$ acts as identity:
$\epsilon\Phi=\bot$ and $\lambda\Phi=\Phi$ for every filesystem $\Phi$.

The command sequences $\alpha$ and $\beta$ are _semantically equivalent_ ,
written as $\alpha\equiv\beta$ if they have the same effect on all
filesystems: $\alpha\Phi=\beta\Phi$ for all $\Phi$. We write
$\alpha\semle\beta$ to denote that _$\beta$ semantically extends $\alpha$_,
that is, $\alpha\Phi=\beta\Phi$ for all filesystems that $\alpha$ does not
break. Clearly, $\alpha\equiv\beta$ if and only if both $\alpha\semle\beta$
and $\beta\semle\alpha$. The sequence $\alpha$ is _non-breaking_ , if there is
a filesystem $\alpha$ does not break. This is the same as requesting
$\alpha\not\equiv\epsilon$.

The _inverse_ of $\sigma=\langle n,x,y\rangle$ is $\sigma^{-1}=\langle
n,y,x\rangle$. For a command sequence $\alpha$ its inverse is defined in the
usual way: $\alpha^{-1}$ consists of the inverse of the commands in $\alpha$
written in reverse order. This inverse has the expected property: if $\alpha$
does not break $\Phi$, then $(\alpha\alpha^{-1})\Phi=\Phi$. In particular,
$\alpha\alpha^{-1}\semle\lambda$.

###  3.3 Command types and execution order

A node value has type $\mathbb{O}$, $\mathbb{D}$, or $\mathbb{F}$ depending on
whether it is the empty value, a directory, or a file. For a command
$\sigma=\langle n,x,y\rangle$ the type of $x$ is its _input type_ and the type
of $y$ is its _output type_. Depending on their input and output types
commands can be partitioned into nine disjoint classes. To make their
descriptions clearer, we use _patterns_. The command $\langle n,x,y\rangle$
matches the pattern $(n,\mathsf{P}_{x},\mathsf{P}_{y})$ if the type of $x$ is
listed in $\mathsf{P}_{x}$ and the type of $y$ is listed in $\mathsf{P}_{y}$.
In a pattern the symbol $\bullet$ matches any value. As an example, every
command matches the pattern
$\langle\bullet,\mathbb{O}\mathbb{F}\mathbb{D},\mathbb{D}\mathbb{F}\mathbb{O}\rangle$.

_Structural commands_ change the type of the stored data, while _transient
commands_ retain it. In other words, commands matching
$\langle\bullet,\mathbb{O},\mathbb{F}\mathbb{D}\rangle$,
$\langle\bullet,\mathbb{F},\mathbb{O}\mathbb{D}\rangle$ or
$\langle\bullet,\mathbb{D},\mathbb{O}\mathbb{F}\rangle$ are structural
commands, while those matching $\langle\bullet,\mathbb{O},\mathbb{O}\rangle$,
$\langle\bullet,\mathbb{F},\mathbb{F}\rangle$ or
$\langle\bullet,\mathbb{D},\mathbb{D}\rangle$ are transient ones. Commands
with identical input and output values are _null commands_. Every null command
is transient, and transient commands which are not null match the pattern
$\langle\bullet,\mathbb{F},\mathbb{F}\rangle$. If $\sigma$ is a null command,
then $\sigma\semle\lambda$ meaning that $\sigma$ does not change the
filesystem (but can break it), and if $\sigma\semle\lambda$ then $\sigma$ is a
null command.

Structural commands are further split into _constructors_ and _destructors_.
Constructor commands upgrade the type from $\mathbb{O}$ to $\mathbb{F}$ to
$\mathbb{D}$, while destructors downgrade it. That is, constructors are
commands matching $\langle\bullet,\mathbb{O},\mathbb{F}\mathbb{D}\rangle$ or
$\langle\bullet,\mathbb{F},\mathbb{D}\rangle$, while the destructors match
$\langle\bullet,\mathbb{D},\mathbb{F}\mathbb{O}\rangle$ or
$\langle\bullet,\mathbb{F},\mathbb{O}\rangle$.

Some command pairs on parent–child nodes can only be executed in a certain
order. This notion is captured by the binary relation $\sigma\ll\tau$ with the
meaning that $\sigma$ must precede $\tau$ in the _execution order_.

[Execution order] For a command pair $\sigma,\tau\in\Omega$ the binary
relation $\sigma\ll\tau$ holds if the pair matches either $\langle
n,\mathbb{D}\mathbb{F},\mathbb{O}\rangle\ll\langle{\uparrow}n,\mathbb{D},\mathbb{F}\mathbb{O}\rangle$
or $\langle{\uparrow}n,\mathbb{O}\mathbb{F},\mathbb{D}\rangle\ll\langle
n,\mathbb{O},\mathbb{F}\mathbb{D}\rangle$. An _$\ll$ -chain_ is a sequence of
commands such that $\sigma_{1}\ll\sigma_{2}\ll\cdots\ll\sigma_{k}$. An
$\ll$-chain _connects_ its first and last element.

The first case in Definition 3.3 of the $\ll$ relation corresponds to the
requirement that a directory cannot be deleted when its descendants are not
empty. The second case requires that before creating a file or directory, the
directory holding it should exist. Observe that $\sigma\ll\tau$ implies that
both $\sigma$ and $\tau$ are structural commands on parent–child nodes, and
either both are constructors or both are destructors. It means that elements
of an $\ll$-chain match either the pattern

$\langle n_{1},\mathbb{D}\mathbb{F},\mathbb{O}\rangle\ll\langle
n_{2},\mathbb{D},\mathbb{O}\rangle\ll\cdots\ll\langle
n_{k-1},\mathbb{D},\mathbb{O}\rangle\ll\langle
n_{k},\mathbb{D},\mathbb{F}\mathbb{O}\rangle$

where $n_{i+1}$ is the parent of $n_{i}$ (we move up along a branch), or they
match

$\langle n_{1},\mathbb{F}\mathbb{O},\mathbb{D}\rangle\ll\langle
n_{2},\mathbb{O},\mathbb{D}\rangle\ll\cdots\ll\langle
n_{k-1},\mathbb{O},\mathbb{D}\rangle\ll\langle
n_{k},\mathbb{O},\mathbb{D}\mathbb{F}\rangle,$

where $n_{i}$ is the parent of $n_{i+1}$ (we move down). Figure 2 illustrates
the structure of $\ll$-chains. The circles represent the nodes on which the
commands act: the top, input type row denotes the types of their values before
executing the commands, while the bottom, output type row shows the types of
their values afterwards. The black arrows point towards the parent nodes, and
the read arrows indicate the execution order.

$\mathbb{D}$$\mathbb{D}$$\mathbb{D}$$\mathbb{D}$$\mathbb{D}\mathbb{F}$input
type$\mathbb{F}\mathbb{O}$$\mathbb{O}$$\mathbb{O}$$\mathbb{O}$$\mathbb{O}$output
type$\sigma_{1}$$\sigma_{2}$$\sigma_{3}$$\sigma_{4}$$\sigma_{5}$command$\mathbb{F}\mathbb{O}$$\mathbb{O}$$\mathbb{O}$$\mathbb{O}$$\mathbb{O}$input
type$\mathbb{D}$$\mathbb{D}$$\mathbb{D}$$\mathbb{D}$$\mathbb{D}\mathbb{F}$output
type$\sigma_{1}$$\sigma_{2}$$\sigma_{3}$$\sigma_{4}$$\sigma_{5}$command Figure
2: Structure of an up (left) and down (right) $\ll$-chain. Black arrows point
to the parent node and red arrows show the execution order $\ll$.

##  4 Canonical sequences and sets

Our synchronizer, including the update detector, relies heavily on the
algebraic structure of internal command sequences. The theory of this
structure has been developed in Csi16  and CC22 . We provide high-level
overviews of the proofs whenever appropriate to make this paper self-contained
and also available to non-experts. For full proofs the reader is referred to
the original papers.

To understand the semantical properties of command sequences, the first step
is to investigate command pairs and determine when they commute, and when they
require a special execution order. Proposition 4 covers the case when the
commands act on the same node, and Proposition 4 considers command pairs on
different nodes.

[(CC22, , Proposition 4)] Suppose $\sigma,\tau\in\Omega$ are on the same node
$n$. Then one of the following two possibilities hold:

  * (a)

$\sigma\tau\semle\omega$ for some $\omega\in\Omega$ also on the same node $n$,

  * (b)

$\sigma\tau\equiv\epsilon$, that is, the pair breaks every filesystem.

###### Proof.

Suppose $\sigma=\langle n,x_{1},y_{1}\rangle$ and $\tau=\langle
n,x_{2},y_{2}\rangle$. If $y_{1}=x_{2}$ then (a) holds with $\omega=\langle
n,x_{1},y_{2}\rangle$. If $y_{1}\neq x_{2}$ then (b) holds: if $\sigma$ does
not break the filesystem, then it leaves $y_{1}$ at node $n$. Now $\tau$
requires $x_{2}$ there, but finds a different value, thus breaks the
filesystem. ∎

For two commands we write
$\sigma\mathbin{\mkern-0.90001mu\parallel\mkern-0.90001mu}\tau$ to mean that
the nodes they act on are uncomparable, i.e., the nodes are different and
neither is an ancestor of the other.

Recall that $\sigma$ is a null command if it has the same input and output
value, that is, it is of the form $\sigma=\langle n,x,x\rangle$.

[(CC22, , Proposition 5)] Suppose $\sigma$ and $\tau$ are non-null commands on
different nodes. Then

  * (a)

if $\sigma\mathbin{\mkern-0.90001mu\parallel\mkern-0.90001mu}\tau$ then
$\sigma\tau\equiv\tau\sigma$, and

  * (b)

if $\sigma\mathbin{\mkern-0.90001mu\nparallel\mkern-0.90001mu}\tau$ then
$\sigma\tau\not\equiv\epsilon$ if and only if $\sigma\ll\tau$.

###### Proof.

By checking all possibilities. ∎

###  4.1 Canonical sequences

Informally, canonical sequences are the “clean” versions of non-breaking
command sequences. The initial definition is a mixture of syntactical and
semantical properties. Proposition 4.1 defines an algorithm which converts any
sequence into a canonical one purification, and Theorem 4.1 gives a complete
syntactical characterization. An important consequence of this
characterization is that the semantics of a canonical sequence is determined
uniquely by the unordered set of commands it contains. It means that the order
of the commands – up to semantical equivalence – can be recovered from their
set only.

[Canonical sequences] A command sequence is _canonical_ if

  * (a)

it does not contain null commands, that is, a command of the form $\langle
n,x,x\rangle$,

  * (b)

no two commands in the sequence are on the same node, and

  * (c)

it is non-breaking.

Conditions (a) and (b) are clearly syntactical, and can be checked by looking
at the commands in the sequence. In Theorem 4.1 below we give a purely
syntactical characterization of canonical sequences. Before stating the
theorem we show that canonical sequences are the “clean” versions of arbitrary
command sequences.

[(Csi16, , Theorem 27)] For every non-breaking command sequence $\alpha$ there
is a canonical sequence $\alpha^{*}$ such that $\alpha\semle\alpha^{*}$, that
is, if $\alpha$ does not break $\Phi$, then both $\alpha$ and $\alpha^{*}$ has
the same effect on $\Phi$.

###### Proof.

Null commands can be deleted from $\alpha$ as they do not change the
filesystem (but may break it). Suppose $\alpha$ has two commands on the same
node. Choose two which are closest to each other; let these be $\sigma_{1}$
and $\sigma_{2}$, both on node $n$. The output value of $\sigma_{1}$ must be
the same as the input value of $\sigma_{2}$ (as $\alpha$ is non-breaking and
the value at node $n$ does not change between $\sigma_{1}$ and $\sigma_{2}$).
Using Proposition 4 $\sigma_{1}$ can be moved forward and/or $\sigma_{2}$ can
be moved backward until the two commands are next to each other (otherwise
$\alpha$ would break every filesystem). Using Proposition 4 the two commands
can be replaced by a single one. ∎

This proof is constructive and specifies a quadratic algorithm which
transforms any non-breaking sequence into a canonical one. To state the purely
syntactical characterization of canonical sequences we need further
definitions.

Let $\alpha$ be a command sequence.

  * (a)

$\alpha$ _honors $\ll$_, if for commands $\sigma,\tau\in\alpha$, $\sigma$
precedes $\tau$ whenever $\sigma\ll\tau$.

  * (b)

$\alpha$ is _$\ll$ -connected_, if for any two commands
$\sigma,\tau\in\alpha$, either
$\sigma\mathbin{\mkern-0.90001mu\parallel\mkern-0.90001mu}\tau$, or $\sigma$
and $\tau$ are connected by an $\ll$-chain (see Definition 3.3) whose elements
are in $\alpha$.

[Syntactical characterization of canonical sequences] A command sequence is
canonical if and only if

  * (a)

it does not contain null commands,

  * (b)

no two commands in the sequence are on the same node,

  * (c1)

it honors $\ll$, and

  * (c2)

it is $\ll$-connected.

###### Proof.

Let $\alpha$ be a canonical sequence according to Definition 4.1. To see that
if either (c1) or (c2) fails then $\alpha$ breaks every filesystem, use
induction on the length of $\alpha$. This shows that if $\alpha$ contains
commands on nodes $n$ and $m$ which lie on the same branch, then $\alpha$ must
contain commands on every node between $n$ and $m$ in the right order.

For the reverse direction assume $\alpha$ satisfies conditions (a), (b), (c1)
and (c2). We create a filesystem which $\alpha$ does not break. The values at
nodes mentioned in the sequence are set to the input values of the commands.
Values at nodes that are ancestors of the ones mentioned in the sequence are
set to directories. Other nodes of the filesystem remain empty. This is a
valid filesystem, and by property (c2) every command in $\alpha$ has the
correct input value. Using property (c1) one can prove that $\alpha$ works on
this filesystem. ∎

###  4.2 Canonical sets

An important consequence of Theorem 4.1 is that the semantics of a canonical
sequence is uniquely determined by the commands it contains. This is expressed
formally in the following Proposition.

[(CC22, , Theorem 14)] If the canonical sequences $\alpha$ and $\beta$ contain
the same commands, then they are semantically equivalent, that is,
$\alpha\Phi=\beta\Phi$ for every filesystem.

###### Proof.

In fact, $\alpha$ and $\beta$ can be transformed into each other using the
commutativity rules given in Proposition 4(a), see (CC22, , Lemma 10). ∎

[Canonical set] The set $A$ of internal commands is _canonical_ if

  * (a)

it does not contains null commands,

  * (b)

no two commands in $A$ are on the same node, and

  * (c2)

the set $A$ is $\ll$-connected, meaning that if two of its commands are on
comparable nodes, then they are connected by an $\ll$-chain whose elements are
in $A$.

Commands in a canonical sequence form a canonical set by Theorem 4.1. In the
other direction, a canonical set can be ordered in many ways to become a
canonical sequence – the only requirement is (c1) which requires that the
order honors the relation $\ll$. This can be achieved by using, e.g.,
topological sort. Any two such orderings give semantically equivalent
sequences, as was proved in Proposition 4.2. Consequently we can, and will,
use canonical sets in places where command sequences are required with the
implicit understanding that the commands in it are ordered in an appropriate
fashion. For example, we write $A\Phi$ to mean $\alpha\Phi$ where $\alpha$
contains the elements of $A$ in an order which honors $\ll$.

Canonical sets play an essential role in reconciliation (Section 5) and
conflict resolution (Section 6). One of their crucial properties is, as we
have seen, that their commands can be executed in different orders while
preserving their semantics – a variant of the _commutativity principle_ of
CRDT PMS09 . Proposition 4.2 discusses the special case when a subset of the
commands should be moved to the beginning of the execution line. Then we
define and investigate _clusters_ in a canonical set, and observe that the
clusters can be freely rearranged, and even intertwined.

For a canonical set $A$ we write $B\Subset A$ to indicate that $B$ is not only
a subset of $A$ but can also be moved to the beginning while keeping the
semantics, namely $A\equiv B\circ(A\smallsetminus B)$.

Let $A$ be a canonical set and $B\subseteq A$. Then $B\Subset A$ if and only
if $\sigma\in A$, $\tau\in B$ and $\sigma\ll\tau$ imply $\sigma\in B$. If
$B\Subset A$ then both $B$ and $A\smallsetminus B$ are canonical.

###### Proof.

An ordering of $A$ does not break every filesystem if and only if it honors
$\ll$, see (CC22, , Lemma 10). Consequently, if $A\equiv
B\circ(A\smallsetminus B)$ then this split must honor $\ll$, which is exactly
the stated condition. If this condition holds, then $A$ has an ordering which
honors $\ll$ and in which $B$ precedes $A\smallsetminus B$.

For the second part it suffices to check that both $B$ and $A\smallsetminus B$
are $\ll$-connected. But it is immediate from the condition and from the fact
that $A$ is $\ll$-connected. ∎

The $\ll$ relation connects commands in a canonical set $A$. The _clusters_ of
$A$ are the components of this connection graph. All commands in a cluster are
constructors, or all commands are destructors, or the cluster has a single
element matching $\langle\bullet,\mathbb{F},\mathbb{F}\rangle$. Accordingly,
we call the cluster _constructor_ , _destructor_ , or _editor_ , respectively.
Nodes of the commands within a cluster form a connected subtree of the
namespace $\mathbb{N}$, and the topmost elements of the subtrees are pairwise
incomparable. In a constructor cluster the “being the parent” and the $\ll$
relations coincide, while in a destructor cluster they are the reverse of each
other, see Figure 2. As feasible orders of the commands in $A$ must only honor
the relation $\ll$, clusters can freely move around. In a constructor cluster
a command can be executed only _after_ all commands on its ancestors have been
executed. In a destructor cluster it is the other way around: a command can be
executed only after all commands on its descendants have been executed. Editor
commands form single-element clusters, thus they can be executed at any point.

###  4.3 The update detector

Algorithms creating the canonical sets required by the reconciler (see Figure
1) are described in Propositions 4.3 and 4.3. The update detector has access
either to the original and modified filesystem (a state-based update
detector), or to the exact command sequence issued by the user (a command-
based update detector). Both algorithms are highly effective, essentially
linear in the input size.

[State-based update detector, (CC22, , Theorem 19)] Let $\Phi$ be the original
filesystem and let $\Phi_{1}$ be the replica. The command set

$A^{*}=\\{\langle n,\Phi(n),\Phi_{1}(n)\rangle:n\in\mathbb{N}\mbox{~{} and
~{}}\Phi(n)\neq\Phi_{1}(n)\,\\}$

is canonical, and $A^{*}\Phi=\Phi_{1}$.

###### Proof.

To show that $A^{*}$ is canonical we need to check that it is $\ll$-connected.
By (Csi16, , Lemma 23) if $n\prec m$ and $\Phi$ and $\Phi_{1}$ differ at $n$
and at $m$, then they must differ at every node between $n$ and $m$. Moreover
the differences follow one of the the patterns on Figure 2, thus these
commands form the required $\ll$-chain. A consequence of this is that $A^{*}$
does not break $\Phi$, and since after executing the commands every node will
have the output value from $\Phi_{1}$, we know $A^{*}\Phi=\Phi_{1}$. ∎

[Command-based update detector] Let $\alpha$ be a command sequence that
transforms the original filesystem $\Phi$ into the replica $\Phi_{1}$. The
following procedure creates a canonical set $A^{*}$ for which
$A^{*}\Phi=\alpha\Phi=\Phi_{1}$. Let $A^{*}$ be empty initially, and iterate
over the commands in $\alpha$ from left to right. Let the next command be
$\sigma$. If there is no command in $A^{*}$ on the same node as $\sigma$, add
$\sigma$ to $A^{*}$. If $\sigma^{*}\in A^{*}$ and $\sigma$ are on the same
node, then using Proposition 4(a) replace $\sigma^{*}$ with the single command
corresponding to the composition $\sigma^{*}\sigma$. Finally, when the
iteration ends, delete the null-commands from $A^{*}$.

###### Proof.

It is clear that the procedure, if implemented properly, is linear in the
length of $\alpha$. Also, on each node of the filesystem the sequence $\alpha$
and the set $A^{*}$ has the same effect. Consequently $A^{*}$ is equivalent to
the command set created in Proposition 4.3, therefore it is canonical. ∎

Original filesystem
$\Phi$$\mathbb{D}$$\mathbb{D}$$\mathbb{D}$$\mathbb{D}$$\mathbb{D}$$\scriptstyle
n_{1}$$\scriptstyle n_{2}$$\scriptstyle n_{3}$$\scriptstyle
n_{4}$$\scriptstyle n_{5}$$\scriptstyle n_{6}$$\scriptstyle
n_{7}$$\scriptstyle n_{8}$$\scriptstyle
n_{9}$$\mathbb{O}$$\mathbb{O}$$\mathbb{O}$$\mathbb{O}$First replica
$\Phi_{1}$$\mathbb{O}$$\mathbb{O}$$\mathbb{O}$$\mathbb{O}$$\mathbb{O}$$\scriptstyle
n_{1}$$\scriptstyle n_{2}$$\scriptstyle n_{3}$$\scriptstyle
n_{4}$$\scriptstyle n_{5}$$\scriptstyle n_{6}$$\scriptstyle
n_{7}$$\scriptstyle n_{8}$$\scriptstyle
n_{9}$$\mathbb{O}$$\mathbb{O}$$\mathbb{O}$$\mathbb{O}$Second replica
$\Phi_{2}$$\mathbb{D}$$\mathbb{D}$$\mathbb{D}$$\mathbb{D}$$\mathsf{f}_{5}$$\scriptstyle
n_{1}$$\scriptstyle n_{2}$$\scriptstyle n_{3}$$\scriptstyle
n_{4}$$\scriptstyle n_{5}$$\scriptstyle n_{6}$$\scriptstyle
n_{7}$$\scriptstyle n_{8}$$\scriptstyle
n_{9}$$\mathsf{f}_{6}$$\mathsf{f}_{7}$$\mathsf{f}_{8}$$\mathsf{f}_{9}$ Figure
3: Illustrating the update detector. The nodes are, from left to right,
$n_{1}$ to $n_{5}$ in the top row, and $n_{6}$ to $n_{9}$ in the bottom row.
The first replica deletes all directories, the second replica stores file
content $\mathsf{f}_{i}$ at node $n_{i}$.

Figure 3 provides two examples for the result of the state-based update
detector. The namespace $\mathbb{N}$ consists of the nodes $n_{1}$ to $n_{9}$.
The original filesystem $\Phi$ contains directories at nodes $n_{1}$ to
$n_{5}$ and the empty value at $n_{6}$ to $n_{9}$. The first replica deletes
all directories, setting the empty value everywhere. The second replica stores
file contents in $n_{5}$ and in the empty nodes. The canonical command set
transforming $\Phi$ into $\Phi_{1}$ consists of the five commands
$A=\\{\sigma_{1},\sigma_{2},\sigma_{3},\sigma_{4},\sigma_{5}\\}$ where
$\sigma_{i}=\langle n_{i},\mathbb{D},\mathbb{O}\rangle$ corresponding to the
five differences between $\Phi$ and $\Phi_{1}$. The second command set also
has five commands $B=\\{\tau_{5},\tau_{6},\tau_{7},\tau_{8},\tau_{9}\\}$ with
$\tau_{5}=\langle n_{5},\mathbb{D},\mathsf{f}_{5}\rangle$ and
$\tau_{i}=\langle n_{i},\mathbb{O},\mathsf{f}_{i}\rangle$ for $i>5$. The set
$A$ has a single execution order honoring $\ll$, namely $\sigma_{5}$,
$\sigma_{4}$, $\sigma_{3}$, $\sigma_{2}$, $\sigma_{1}$. Any ordering of the
commands in $B$ honors $\ll$, as no two commands in $B$ are $\ll$-related.

##  5 The reconciler – synchronizing two replicas

The update detector – either state-based or operation-based – passes the
canonical sets $A$ and $B$ to the reconciler, see Figure 1. These sets
describe, in a straightforward and intuitive way, how the replicas $\Phi_{1}$
and $\Phi_{2}$ relate to the original filesystem $\Phi$. As discussed in
Section 2, the merged filesystem is also specified by a canonical set $M$
(that of the sequence $\mu$) to be applied to the original $\Phi$. The next
definition, which is the formalization of the informal discussion about
synchronization, _declares_ when $M$ represents an intuitively correct
synchronization.

[Merger command set] The _merger_ of the canonical sets $A$ and $B$ is a
maximal canonical set $M\subseteq A\cup B$, meaning that no proper superset of
$M$ within $A\cup B$ is canonical.

Note that the merger $M$ is not necessarily unique, and typically many
different mergers exist (see the example below). This definition covers every
permissible synchronization outcome which satisfies both the _intention-
confined effect_ ($M$ is a subset of $A\cup B$) and the _aggressive effect
preservation_ ($M$ is maximal) requirements. When performing the actual file
synchronization, one of the mergers should be chosen, either by the system or
the user. Section 6 discusses how this choice can be made by successive
conflict resolutions.

In this section we prove that every synchronized state defined by a merger $M$
has a clear operational characterization: both replicas can be transformed
into the merged state by first rolling back some of the commands executed
earlier on this replica, and then applying some commands executed on the other
replica. Using the terminology of CC22 , the canonical sets $A$ and $B$ are
called _refluent_ if there is filesystem on which both of them works (neither
of them breaks). This condition is clearly met when $A$ and $B$ describe two
replicas, as both are applied to their common original filesystem.

Let $A$ and $B$ be refluent canonical sets and $M\subseteq A\cup B$ be a
merger. Then

  * (a)

$M\semge A\circ A_{1}^{-1}\circ B^{\prime}$, where $A_{1}=A\smallsetminus
M\subseteq A$ and $B^{\prime}=M\smallsetminus A\subseteq B$,

  * (b)

$M\semge B\circ B_{1}^{-1}\circ A^{\prime}$ where $B_{1}=B\smallsetminus
M\subseteq B$ and $A^{\prime}=M\smallsetminus B\subseteq A$,

  * (c)

if both $A$ and $B$ are applicable to a filesystem, then so are $M$, $A\circ
A_{1}^{-1}\circ B^{\prime}$ and $B\circ B_{1}^{-1}\circ A^{\prime}$.

In case of synchronizing the replicas $\Phi_{1}=A\Phi$ and $\Phi_{2}=B\Phi$,
let $\Psi=M\Phi$ be (one of) the merged filesystems. According to this
theorem, we have

$\begin{array}[]{l}\Psi=M\Phi=(A\circ A_{1}^{-1}\circ
B^{\prime})\Phi=B^{\prime}(A_{1}^{-1}\Phi_{1}),\mbox{~{}~{} and}\\\\[4.0pt]
\Psi=M\Phi=(B\circ B_{1}^{-1}\circ
A^{\prime})\Phi=A^{\prime}(B_{1}^{-1}\Phi_{2}).\end{array}$

The first line says that the replica $\Phi_{1}$ can be transformed into the
synchronized filesystem $\Psi$ first by applying $A_{1}^{-1}$, that is,
rolling back those commands in $A$ which are not in $M$, and then applying
some further commands $B^{\prime}$ from $B$. The similar statement for the
other replica $\Phi_{2}$ follows from the second line. This justifies the
informal statement in Section 2.

Merged copy
$\Psi_{1}$$\mathbb{D}$$\mathbb{D}$$\mathbb{D}$$\mathbb{D}$$\mathbb{O}$$\scriptstyle
n_{1}$$\scriptstyle n_{2}$$\scriptstyle n_{3}$$\scriptstyle
n_{4}$$\scriptstyle n_{5}$$\scriptstyle n_{6}$$\scriptstyle
n_{7}$$\scriptstyle n_{8}$$\scriptstyle
n_{9}$$\mathsf{f}_{6}$$\mathsf{f}_{7}$$\mathsf{f}_{8}$$\mathsf{f}_{9}$Merged
copy
$\Psi_{2}$$\mathbb{D}$$\mathbb{D}$$\mathbb{D}$$\mathbb{O}$$\mathbb{O}$$\scriptstyle
n_{1}$$\scriptstyle n_{2}$$\scriptstyle n_{3}$$\scriptstyle
n_{4}$$\scriptstyle n_{5}$$\scriptstyle n_{6}$$\scriptstyle
n_{7}$$\scriptstyle n_{8}$$\scriptstyle
n_{9}$$\mathsf{f}_{6}$$\mathsf{f}_{7}$$\mathsf{f}_{8}$$\mathbb{O}$Merged copy
$\Psi_{3}$$\mathbb{D}$$\mathbb{O}$$\mathbb{O}$$\mathbb{O}$$\mathbb{O}$$\scriptstyle
n_{1}$$\scriptstyle n_{2}$$\scriptstyle n_{3}$$\scriptstyle
n_{4}$$\scriptstyle n_{5}$$\scriptstyle n_{6}$$\scriptstyle
n_{7}$$\scriptstyle n_{8}$$\scriptstyle
n_{9}$$\mathsf{f}_{6}$$\mathbb{O}$$\mathbb{O}$$\mathbb{O}$ Figure 4: Three
possible results of synchronizing the filesystems in Figure 3

Theorem 5 is illustrated on the filesystems in Figure 3. The canonical sets
transforming the original filesystem to the replicas are
$A=\\{\sigma_{1},\sigma_{2},\sigma_{3},\sigma_{4},\sigma_{5}\\}$ (where
$\sigma_{i}=\langle n_{i},\mathbb{D},\mathbb{O}\rangle$) and
$B=\\{\tau_{5},\tau_{6},\tau_{7},\tau_{8},\tau_{9}\\}$ (where
$\tau_{i}=\langle n_{i},\mathbb{O}\mathbb{D},\mathsf{f}_{i}\rangle$),
respectively. The synchronized states shown on Figure 4 correspond to the
mergers $M_{1}=\\{\sigma_{5},\tau_{6},\tau_{7},\tau_{8},\tau_{9}\\}$,
$M_{2}=\\{\sigma_{4},\sigma_{5},\tau_{6},\tau_{7},\tau_{8}\\}$, and
$M_{3}=\\{\sigma_{2},\sigma_{3},\sigma_{4},\sigma_{5},\tau_{6}\\}$,
respectively. Altogether there are six mergers of $A$ and $B$ depending on how
many levels of the directory erasures in $A$ are kept. To get $\Psi_{1}$ from
the replica $\Phi_{1}$ we first roll back the commands $\sigma_{1}$,
$\sigma_{2}$, $\sigma_{3}$ and $\sigma_{4}$ in this order (commands in the set
$A\smallsetminus M_{1}$), which restores the four directories. Then we apply
the commands $\tau_{6}$, $\tau_{7}$, $\tau_{8}$, $\tau_{9}$ from the other
command set $B$ to set the file values. Getting $\Psi_{1}$ from the second
replica requires fewer commands. First roll back $\tau_{5}$ (the only member
of $B\smallsetminus M_{1}$) restoring the directory at $n_{5}$, then apply
$\sigma_{5}$ to erase this directory.

The proof of Theorem 5 uses some intricate properties of canonical sets and
mergers which we prove first.

Let $A$ and $B$ be refluent canonical sets with $\tau\in A$, $\sigma\in A\cup
B$ and $\sigma\ll\tau$. Then $\sigma\in A$.

###### Proof.

Let $\sigma$, $\tau$ be on nodes $n$ and $m$, respectively, and $\Phi$ be any
filesystem on which both $A$ and $B$ work. The value $\Phi(n)$ is the input
value of $\sigma$, and $\Phi(m)$ is the input value of $\tau$. Now
$\sigma\ll\tau$ matches either the pattern $\langle
n,\mathbb{D}\mathbb{F},\mathbb{O}\rangle\ll\langle{\uparrow}n,\mathbb{D},\mathbb{F}\mathbb{O}\rangle$
or the pattern
$\langle{\uparrow}m,\mathbb{O}\mathbb{F},\mathbb{D}\rangle\ll\langle
m,\mathbb{O},\mathbb{F}\mathbb{D}\rangle$, see Definition 3.3. If $A$ has no
command on node $n$, then executing $\tau$ would break $\Phi$ as $\Phi(n)$
still has its original value. Thus let $\sigma^{\prime}\in A$ be on node $n$.
The input value of $\sigma^{\prime}$ is the same as that of $\sigma$, moreover
$\sigma^{\prime}\ll\tau$ (as $A$ is canonical and $\sigma^{\prime}$ and $\tau$
are on parent–child nodes). Then the output values of $\sigma^{\prime}$ and
$\sigma$ are also equal since they are either both $\mathbb{O}$ or
$\mathbb{D}$, thus $\sigma=\sigma^{\prime}$. ∎

A similar statement holds for mergers, but the proof is more involved.

Let $A$ and $B$ be refluent canonical sets, $M\subseteq A\cup B$ be a merger
with $\tau\in M$, $\sigma\in A\cup B$ and $\sigma\ll\tau$. Then $\sigma\in M$.

###### Proof.

Let $\sigma$ and $\tau$ be a lowest counterexample to the claim, and $n$ and
$m$ be their respective nodes. By “lowest” we mean that there is no other
counterexample pair $\sigma^{*},\tau^{*}$ where the node of $\sigma^{*}$ would
be below $n$.

The argument of the proof of Propostion 5 gives that if $M$ has a command on
$n$ (the node of $\sigma$), then $\sigma\in M$. Thus $\sigma$ cannot be added
to $M$ only if $M$ already contains a command $\sigma^{\prime}$ on a node
$n^{\prime}$ such that $n^{\prime}$ and $n$ are comparable and
$\sigma^{\prime}$ and $\sigma$ cannot be connected by an $\ll$-chain. If $m$
and $n^{\prime}$ are comparable, then there is an $\ll$-chain in $M$ between
$\tau$ and $\sigma^{\prime}$ as both are in $M$. As no command in $M$ is on
$n$, the node $n$ cannot be between $m$ and $n^{\prime}$. But then
$\sigma\ll\tau\ll\cdots\ll\sigma^{\prime}$ is an $\ll$-chain in $M$ connecting
$\sigma$ and $\sigma^{\prime}$, a contradiction. (Note that the chain between
$\tau$ and $\sigma^{\prime}$ cannot be in the other direction.)

Therefore $m$ and $n^{\prime}$ are uncomparable, which means that $m$ and
$n^{\prime}$ are both below $n$, consequently $\sigma$ and $\tau$ are
constructors. Let $\Phi$ be any filesystem on which both $A$ and $B$ work. As
$\sigma$ matches $\langle n,\mathbb{O}\mathbb{F},\mathbb{D}\rangle$, $\Phi(n)$
is either empty or is a file. It means that all nodes below $n$ are empty, in
particular $\Phi(n^{\prime})=\mathbb{O}$, and $\sigma^{\prime}$ changes this
empty value to something else. Now suppose $\sigma^{\prime}\in A$. As $A$ does
not break $\Phi$, it must change the non-directory value at $n$ to a
directory, consequently $\sigma\in A$ as well. Then there is an $\ll$-chain
between $\sigma$ and $\sigma^{\prime}$ in A starting with $\sigma$ and ending
with $\sigma^{\prime}\in M$. As $\sigma$ was chosen to be the lowest
counterexample, all elements of this chain are in $M$, which is a
contradiction again. ∎

Recall from Proposition 4.2 that $B\Subset A$ if and only if $B\subseteq A$
and there are no $\sigma\ll\tau$ such that $\tau\in B$ and $\sigma\in
A\smallsetminus B$.

Let $A$, $B$ be refluent canonical sets, and $M$ be a merger. Then $A\cap
M\Subset A$, and $A\cap M\Subset M$.

###### Proof.

Both statements follow from the combination of Propositions 5 and 5. If
$\tau\in A\cap M$ and $\sigma\ll\tau$ with $\sigma\in A\cup B$, then
$\sigma\in A\cap M$. ∎

Claim (a) of Theorem 5 follows immediately from Proposition 5. Let
$A_{2}=A\cap M$, $A_{1}=A\smallsetminus M$, and $B^{\prime}=M\smallsetminus
A$. By Propositions 5 and 4.2 we have $A=A_{2}\circ A_{1}$, and $M=A_{2}\circ
B^{\prime}$. Thus

$M=A_{2}\circ B^{\prime}\semge(A_{2}\circ A_{1}\circ A_{1}^{-1})\circ
B^{\prime}=A\circ A_{1}^{-1}\circ B^{\prime},$

and a similar reasoning gives claim (b).

Recall that the notation
$\sigma\mathbin{\mkern-0.90001mu\parallel\mkern-0.90001mu}\tau$ means that the
nodes which the commands $\sigma$ and $\tau$ are acting on are uncomparable
(that is, independent). We write
$\sigma\mathbin{\mkern-0.90001mu\parallel\mkern-0.90001mu}B$ to mean that for
every $\tau\in B$ we have
$\sigma\mathbin{\mkern-0.90001mu\parallel\mkern-0.90001mu}\tau$, and
$A\mathbin{\mkern-0.90001mu\parallel\mkern-0.90001mu}B$ to mean that for every
$\sigma\in A$ we have
$\sigma\mathbin{\mkern-0.90001mu\parallel\mkern-0.90001mu}B$.

Suppose that the canonical sets $A$ and $B$ are applicable to the filesystem
$\Phi$; moreover, $A\smallsetminus
B\mathbin{\mkern-0.90001mu\parallel\mkern-0.90001mu}B\smallsetminus A$. Then
$A\cup B$ is canonical and is applicable to $\Phi$.

###### Proof.

First we show that $A\cup B$ is canonical. This is so as $A\smallsetminus B$
and $B\smallsetminus A$ do not have commands on comparable or coinciding
nodes, thus any two commands in $A\cup B$ on comparable nodes are both in $A$,
or are both in $B$. Second, $A\cup B$ is applicable to $\Phi$ when $A$ and $B$
are disjoint as in this case, by assumption,
$A\mathbin{\mkern-0.90001mu\parallel\mkern-0.90001mu}B$, see also (Csi16, ,
Lemma 36).

When $A$ and $B$ are not disjoint, let $C=A\cap B$. By Proposition 5,
$C\Subset A$, thus $A\equiv C\circ(A\smallsetminus C)$ which means
$A\Phi=(A\smallsetminus C)(C\Phi)$. Similarly, $B\Phi=(B\smallsetminus
C)(C\Phi)$. Applying the first case of this proof to the dijoint sets
$A\smallsetminus C$, $B\smallsetminus C$ and the filesystem $C\Phi$ shows that
$(A\cup B)\smallsetminus C$ is applicable to $C\Phi$. Since $C\Subset(A\cup
B)$ also holds, we get that $A\cup B$ is applicable to $\Phi$. ∎

After these preparations claim (c) of Theorem 5 can be proved as follows. Let
$A_{2}=A\cap M$ and $B_{2}=B\cap M$. Then $A_{2}\cup B_{2}=M$ and
$M\smallsetminus A_{2}=B_{2}\smallsetminus A_{2}$. Now $A_{2}\Subset M$ by
Proposition 5, which means that $A_{2}$ is canonical and $M\equiv
A_{2}\circ(M\smallsetminus A_{2})=A_{2}\circ(B_{2}\smallsetminus A_{2})$, and
similarly $M\equiv B_{2}\circ(A_{2}\smallsetminus B_{2})$. We claim that
$A_{2}\smallsetminus
B_{2}\mathbin{\mkern-0.90001mu\parallel\mkern-0.90001mu}B_{2}\smallsetminus
A_{2}$. This is because these sets are disjoint and if $\sigma$ in the first
set and $\tau$ in the second set are on comparable nodes, then they are
$\ll$-connected (as both are in the canonical set $M$), thus in any ordering
of $M$ which honors $\ll$ they are in a fixed order. But in
$A_{2}\circ(B_{2}\smallsetminus A_{2})$ $\sigma$ comes before $\tau$, and in
$B_{2}\circ(A_{2}\smallsetminus B_{2})$ $\tau$ comes before $\sigma$, which is
a contradiction.

Let $\Phi$ be a filesystem to which both $A$ and $B$ can be applied. Again by
Proposition 5, $A_{2}\Subset A$, thus $A_{2}$ is also applicable to $\Phi$,
and similarly $B_{2}$ is applicable to $\Phi$. By Proposition 5, $M=A_{2}\cup
B_{2}$ is also applicable to $\Phi$, which is the first claim in Theorem 5
(c). For the other two claims observe that $A_{1}=A\smallsetminus
M=A\smallsetminus A_{2}$ and $B^{\prime}=M\smallsetminus A=M\smallsetminus
A_{2}$. We know $A_{2}\Subset A$, thus $A\circ A_{1}^{-1}=A_{2}\circ
A_{1}\circ A_{1}^{-1}$, which is applicable to $\Phi$ and gives $A_{2}\Phi$.
Since $A_{2}\Subset M$ and $M$ is applicable to $\Phi$, $M\smallsetminus
A_{2}=B^{\prime}$ is applicable to $A_{2}\Phi$. All together, $A\circ
A_{1}^{-1}\circ B^{\prime}$ is applicable to $\Phi$, as claimed.

##  6 Synchronization by conflict resolution

In the realm of file synchronization a _conflict_ is represented by two
filesystem commands which can be executed individually, but not together.
Resolving the conflict means choosing one of the following actions (see, among
others, syncpal-thesis ; NS16 ):

  * •

discard both commands,

  * •

discard one command and keep the other (loser/winner paradigm), or

  * •

replace one or both commands by a new one.

Only the second alternative satisfies both the _intention-confined effect_
principle R1 (use only commands issued by the user), and the _aggressive
effect preservation_ principle R2 (carry over as many operations as possible).
Our synchronizer uses this loser/winner paradigm to solve all conflicts.
Resolving a conflict might create new ones, or automatically solve – or make
irrelevant – others. Thus after each step the set of conflicts has to be
regenerated, or at least revalidated/reviewed. Termination of the
synchronization process is not automatic and has to be proved, see syncpal-
thesis . Fortunately, in our case no new conflicts are generated, and resolved
and disappearing conflicts can be identified easily. As each step eliminates
at least one conflict, the synchronizer clearly stops after finitely many
steps.

###  6.1 Theoretical foundation

In this subsection we fix the refluent canonical sets $A$ and $B$ and the
merger $M$ which the synchronization is supposed to reach, but is not
necessarily known at the start. First we show that synchronization can be
reduced to the case when $A$ and $B$ are disjoint (though they might contain
different commands on the same node). Then we define when a command pair
represents a _conflict_ , and show that this notion has the expected
properties: a merger $M$ does not contain conflicting pairs, and if there are
no conflicts, then $M$ is the disjoint union of $A$ and $B$. The main novelty
of our conflict resolution algorithm is that instead using the winner to build
up the merger, it only discards the losing command from future considerations.
In other words, the algorithm thins out the sets $A$ and $B$ until only the
merger $M$ remains.

Let $A,B$ be refluent canonical sets, and $M$ be a merger. Then (a) $A\cap
B\Subset A$ and $A\cap B\Subset B$, (b) $A\cap B\subseteq M$, and (c) $A\cap
B\Subset M$.

###### Proof.

Claim (a) follows from Proposition 5 since if $\tau\in A\cap B$, $\sigma\in
A\cup B$ and $\sigma\ll\tau$, then $\sigma\in A\cap B$. From this and from (b)
claim (c) follows, too.

To prove (b) it suffices to check that $M\cup(A\cap B)$ is canonical. First,
all commands in this union are on different nodes. Both $M$ and $A\cap B$ are
canonical, so if their union were not, then there are commands $\sigma\in
A\cap B$ and $\sigma^{\prime}\in M\smallsetminus(A\cap B)$ on comparable nodes
which are not connected by an $\ll$-chain in $M\cup(A\cap B)$. Assume
$\sigma^{\prime}\in A$. There is a chain between $\sigma$ and
$\sigma^{\prime}$ in $A$. Since $A\cap B\Subset A$, we know this chain has the
direction $\sigma\ll\cdots\ll\sigma^{\prime}$. From this and because
$\sigma^{\prime}\in M$, we know all members of this chain are in $M$ based on
Proposition 5, which is a contradiction. ∎

Let $C=A\cap B$ and let $\Phi$ be a filesystem which shows that $A$ and $B$
are refluent, that is, both $A$ and $B$ work on $\Phi$. Let
$A^{\prime}=A\smallsetminus C$, $B^{\prime}=B\smallsetminus C$, and
$M^{\prime}=M\smallsetminus C$; observe that the command sets $A^{\prime}$ and
$B^{\prime}$ are disjoint. By Proposition 6.1 $C$ is canonical and can be
moved to the front of $A$ and $B$ and $M$; moreover $A^{\prime}$ and
$B^{\prime}$ and $M^{\prime}$ are also canonical. Now $A^{\prime}$ and
$B^{\prime}$ are refluent (both are applicable to $C\Phi$), and $M^{\prime}$
is a merger for $A^{\prime}$ and $B^{\prime}$. The converse of the last
statement is also true: if $M^{*}$ is any merger of $A^{\prime}$ and
$B^{\prime}$, then $C\cup M^{*}$ is a merger of $A$ and $B$. Consequently it
suffices to find the merger $M^{\prime}$ of the disjoint command sets
$A^{\prime}$ and $B^{\prime}$, and then adding the intersection $A\cap B$ to
$M^{\prime}$. For this reason, from this point on we assume that $A$ and $B$
share no commands.

Let $A$ and $B$ be fixed disjoint, refluent canonical sets. The pair
$(\sigma,\tau)$ is a _conflict_ if $\sigma\in A$, $\tau\in B$ and
$\sigma\mathbin{\mkern-0.90001mu\nparallel\mkern-0.90001mu}\tau$, that is, the
nodes of $\sigma$ and $\tau$ are comparable (including when they coincide).

The _conflict graph_ is the bipartite graph with the disjoint command sets $A$
and $B$ as the two classes, and an edge between $\sigma\in A$ and $\tau\in B$
if they are in conflict. Figure 5 a) shows the conflict graph of the
synchronization problem depicted on Figure 3. As an example, command
$\sigma_{5}$ is connected to $\tau_{5}$ only, as both $\sigma_{5}$ and
$\tau_{5}$ are on node $n_{5}$, while $n_{5}$ is independent of the nodes
$n_{6}$, …, $n_{9}$ on which the other commands in $B$ are.

$\sigma_{1}$$\sigma_{2}$$\sigma_{3}$$\sigma_{4}$$\sigma_{5}$$\tau_{6}$$\tau_{7}$$\tau_{8}$$\tau_{9}$$\tau_{5}$a)$\sigma_{1}$$\sigma_{2}$$\sigma_{3}$$\sigma_{4}$$\sigma_{5}$$\tau_{6}$$\tau_{7}$$\tau_{8}$$\tau_{9}$$\tau_{5}$b)$\sigma_{1}$$\sigma_{2}$$\sigma_{3}$$\sigma_{4}$$\sigma_{5}$$\tau_{6}$$\tau_{7}$$\tau_{8}$$\tau_{9}$$\tau_{5}$c)
Figure 5: a) The conflict graph of the synchronization problem of Figure 3.
The conflict $(\sigma_{2},\tau_{7})$ is resolved with the winner $\tau_{7}$.
b) The conflict graph after resolving $(\sigma_{2},\tau_{7})$; commands
$\sigma_{1}$ and $\sigma_{2}$ are deleted. The next conflict we resolve is
$(\sigma_{4},\tau_{5})$.
c) The conflict graph after resolving $(\sigma_{4},\tau_{5})$ with the winner
$\sigma_{4}$; commands $\tau_{9}$, $\tau_{5}$ are deleted. The final conflict
graph contains the commands $\sigma_{4}$, $\sigma_{5}$, $\tau_{6}$,
$\tau_{7}$, $\tau_{8}$, and no edges.

It is impossible that both commands of the conflict $(\sigma,\tau)$ are in
$M$.

###### Proof.

The meanings of the symbols are as in Definition 6.1. Suppose by contradiction
that both are in $M$. As they are on comparable nodes, there is an $\ll$-chain
in $M$ between $\sigma$ and $\tau$. Consequently there are two consecutive
commands in this chain so that one is in $A$ and the other is in $B$, say
$\sigma^{\prime}\ll\tau^{\prime}$, $\sigma^{\prime}\in A$ and
$\tau^{\prime}\in B$. But Proposition 5 says that in this case
$\sigma^{\prime}\in B$, contradicting that $A$ and $B$ are disjoint. ∎

Suppose $(\sigma,\tau)$ is a conflict, $\sigma^{\prime}\in A$ and
$\sigma\ll\sigma^{\prime}$. Then $(\sigma^{\prime},\tau)$ is also a conflict.

###### Proof.

Let $\sigma$, $\sigma^{\prime}$ be on nodes $n$ and $n^{\prime}$,
respectively. If $n^{\prime}$ is the parent of $n$, then the node of $\tau$ is
comparable to $n^{\prime}$, thus we are done. Therefore $n$ is the parent of
$n^{\prime}$, $\sigma$ and $\sigma^{\prime}$ are constructors, and $\sigma$
matches $\langle n,\mathbb{O}\mathbb{F},\mathbb{D}\rangle$. If the node of
$\tau$ is not below $n$, then we are done. If it is, then the input type of
$\tau$ is $\mathbb{O}$ (as in the original filesystem $\Phi$, $\Phi(n)$ is not
a directory, therefore every node below it is empty). For the same reason the
command set $B$ must contain a command on node $n$ (otherwise when executing
$\tau$, $\Phi$ still has the original content at $n$, and then $\tau$ breaks
$\Phi$). This command has the same input type as $\sigma$, must create a
directory, thus it is equal to $\sigma$, contradicting that $A$ and $B$ are
disjoint. ∎

By symmetry, the same claim holds when $A$ and $B$ are swapped. Fix $\sigma\in
A$, and split $B$ into $B^{\mathsf{ok}}_{\sigma}$ and
$B^{\mathsf{conf}}_{\sigma}$ as follows:

$\begin{array}[]{r@{\;=\;}l}B^{\mathsf{ok}}_{\sigma}&\\{\tau\in B:\mbox{
$(\sigma,\tau)$ \emph{is not} a conflict}\\}=\\{\tau\in
B:\sigma\mathbin{\mkern-0.90001mu\parallel\mkern-0.90001mu}\tau\\},\\\\[4.0pt]
B^{\mathsf{conf}}_{\sigma}&\\{\tau\in B:\mbox{ $(\sigma,\tau)$ \emph{is} a
conflict}\\}=\\{\tau\in
B:\sigma\mathbin{\mkern-0.90001mu\nparallel\mkern-0.90001mu}\tau\\}.\end{array}$

We know $B^{\mathsf{ok}}_{\sigma}\Subset B$ by Propositions 4.2 and 6.1, which
means that if $\Phi$ is a filesystem $B$ does not break, then neither does
$B^{\mathsf{ok}}_{\sigma}$. Also, if $\sigma\ll\sigma^{\prime}$, then
$B^{\mathsf{conf}}_{\sigma}\subseteq B^{\mathsf{conf}}_{\sigma^{\prime}}$. In
particular, if $B^{\mathsf{conf}}_{\sigma^{\prime}}$ is empty, then so is
$B^{\mathsf{conf}}_{\sigma}$. Next we show that if there are no conflicts,
then the synchronization is done; however, we need a stronger statement which
will be used to justify the correctness of the synchronization process.

Suppose $B^{\mathsf{conf}}_{\sigma}$ is empty, that is, no $\tau\in B$ is in
conflict with $\sigma\in A$. Then $\sigma\in M$.

###### Proof.

It is enough to show that $M\cup\\{\sigma\\}$ is canonical. Since
$\sigma\mathbin{\mkern-0.90001mu\parallel\mkern-0.90001mu}B$, it has at most
one command on every node. It can only be non-canonical if there is a $\tau\in
M$ on a related node that cannot be connected to $\sigma$ using an $\ll$-chain
from the commands in $M$. This $\tau$ must be in $A$, which has a chain
between $\sigma$ and $\tau$. If this chain goes in the direction
$\sigma\ll\cdots\ll\tau$, then $\sigma\in M$ by Proposition 5. Otherwise we
know $\tau\ll\cdots\ll\sigma$, and based on the remark above,
$B^{\mathsf{conf}}_{\omega}$ is empty for all members of this chain and so are
independent of $B$. This means the chain can be added to $M$, which is a
contradiction. ∎

[Termination] If there are no conflicts, then the merger $M$ is $A\cup B$.

###### Proof.

By Proposition 6.1 every command in $A$ is in $M$, and similarly $B\subseteq
M$. As $M$ is a subset of $A\cup B$, they must be equal. ∎

###  6.2 The synchronization algorithm

The input of the synchronization algorithm is $(A^{o}$, $B^{o})$, a pair of
refluent canonical command sets. The goal is to find, using successive
conflict resolution steps, a merger command set $M$ that fits Definition 5.
Moreover, we aim to show that our algorithm can produce _any_ of the mergers
allowed by the definition, and only valid mergers. To achieve this, the
algorithm accepts a pre-set merger $M^{o}$ as an optional argument. Whenever
the algorithm needs to make an otherwise arbitrary choice, $M^{o}$ is used to
choose one of the possibilities. While choosing any of the possibilities will
generate a valid merger, guiding the choice will guarantee that $M^{o}$ will
be generated.

As described in the previous section, the first step is to reduce the problem
to the case when the command sets $A^{o}$ and $B^{o}$ have no common elements.
[Synchronization in the general case]Let $C=A^{o}\cap B^{o}$. Execute
Algorithm 6.2 with the command sets $A^{o}\smallsetminus C$ and
$B^{o}\smallsetminus C$. If $M^{o}$ is specified, then it must satisfy
$C\subseteq M^{o}$; in this case pass $M^{o}\smallsetminus C$ as the optional
input to Algorithm 6.2. When Algorithm 6.2 returns $M$, return $C\cup M$.

###### Correctness of Algorithm 6.2.

As discussed after the proof of Proposition 6.1, $A^{o}\smallsetminus C$ and
$B^{o}\smallsetminus C$ are refluent canonical sets, and $C$ is an initial
segment of every merger of $A^{o}$ and $B^{o}$. Moreover, if $M^{o}$ is a
merger of $A^{o}$ and $B^{o}$, then $M^{o}\smallsetminus C$ is a merger of
$A^{o}\smallsetminus C$ and $B^{o}\smallsetminus C$. ∎

Inputs of the main Algorithm 6.2 are the _disjoint_ refluent canonical sets
$A^{o}$ and $B^{o}$, and the optional target merger $M^{o}$ of $A^{o}$ and
$B^{o}$. The goal is to produce a merger $M$. If $M^{o}$ is given, then, at
the end, $M$ and $M^{o}$ must be equal.

The algorithm maintains two command sets $A$ and $B$, initially set to $A^{o}$
and $B^{o}$. During execution these sets satisfy the following invariants:

  * 1.

$A\Subset A^{o}$, $B\Subset B^{o}$, consequently $A$ and $B$ are refluent
canonical subsets of $A^{o}$ and $B^{o}$;

  * 2.

all mergers of $A$ and $B$ are mergers of $A^{o}$ and $B^{o}$;

  * 3.

if $M^{o}$ is specified, then $M^{o}$ is a merger of $A$ and $B$.

In each iteration one or more commands are deleted either from $A$ or from $B$
until only the commands of the merger remain.

[Synchronization of disjunct sets]Initialization:  Set $A\leftarrow A^{o}$ and
$B\leftarrow B^{o}$.

  * Iterate:  Choose $\sigma\in A$ and $\tau\in B$ such that $(\sigma,\tau)$ is a conflict. If no such pair exists, go to Finish. If $M^{o}$ is given, choose a conflict so that either $\sigma$ or $\tau$ is in $M^{o}$.

Conflict resolution:  Out of $\sigma$ and $\tau$, choose the _winner_ and the
_loser_ commands. If $M^{o}$ is given, let the winner be the one in $M^{o}$.
If $\sigma$ is the winner, delete all commands from $B$ which are in conflict
with $\sigma$ (including $\tau$). If $\tau$ is the winner, delete all commands
from $A$ which are in conflict with $\tau$. Go back to Iterate.

  * Finish:  Return $A\cup B$ as the merger.

Execution of Algorithm 6.2 is illustrated in Figure 5. The initial command
sets are $A=\\{\sigma_{1},\dots,\sigma_{5}\\}$ and
$B=\\{\tau_{6},\dots,\tau_{5}\\}$. In the first iteration $\tau_{7}\in B$ is
the winner; therefore, commands in $A$ which are in conflict with $\tau_{7}$
($\sigma_{1}$ and $\sigma_{2}$) are removed from $A$. In the next iteration
the winner is $\sigma_{4}\in A$, and $\tau_{9}$ and $\tau_{5}$ are removed
from $B$. In the last iteration $\sigma_{3}$ is removed from $A$, thus the
remaining sets are $A=\\{\sigma_{4},\sigma_{5}\\}$ and
$B=\\{\tau_{6},\tau_{7},\tau_{8}\\}$. The returned merger is $A\cup B$.

###### Correctness of Algorithm 6.2.

After the initialization step all three invariants hold. The algorithm
terminates as in each iteration the total number of remaining conflicts
strictly decreases. When it terminates, the returned set $A\cup B=M$ is a
merger of the original command sets $A^{o}$ and $B^{o}$. This is because at
that point there are no conflicts between $A$ and $B$, thus, by Corollary 5,
$M$

is a merger of $A$ and $B$—in fact, the only one—, and then the second
invariant guarantees that $M$ is also a merger of $A^{o}$ and $B^{o}$. If
$M^{o}$ was submitted to the algorithm, then the third invariant ensures
$M=M^{o}$. Thus we only need to show that the iteration preserves all three
invariants. Suppose there is a conflict $(\sigma,\tau)$ between $A$ and $B$,
and the winner of the conflict is $\sigma\in A$.

Invariant 1. Commands in conflict with $\sigma$ are deleted from $B$, thus $B$
is replaced by the set

$B^{\mathsf{ok}}_{\sigma}=\\{\tau^{\prime}\in B:\mbox{
$(\sigma,\tau^{\prime})$ is not a conflict}\\}.$

Proposition 6.1 (see the discussion following the proof) and the invariant
imply $B^{\mathsf{ok}}_{\sigma}\Subset B\Subset B^{o}$. Consequently the
invariant $B\Subset B^{o}$ remains true.

Invariant 2. We know that if a merger of $A$ and $B$ contains $\sigma$, then
it cannot contain any of the discarded elements of $B$ (see Proposition 6.1).
We also know that all mergers of $A$ and $B^{\mathsf{ok}}_{\sigma}$ contain
$\sigma$ by Proposition 6.1 as it is not in conflict with any other command.
Consequently the set of mergers of $A$ and $B^{\mathsf{ok}}_{\sigma}$ consists
of those mergers of $A$ and $B$ that contain $\sigma$, and the invariant
continues to hold.

Invariant 3. If $M^{o}$ was specified for the algorithm, then we chose the
winner accordingly, and so $\sigma\in M^{o}$. A consequence of the discussion
above is that $M^{o}$ remains part of the set of mergers of $A$ and
$B^{\mathsf{ok}}_{\sigma}$.

Finally we show that if $M^{o}$ is specified, then one of the conflicting
commands can be chosen from $M^{o}$. By Proposition 6.1 if $\sigma\in A$ is
not in conflict with any command in $B$, then $\sigma$ is in every merger of
$A$ and $B$; in particular, it is in $M^{o}$ by the third invariant. Thus, if
no conflicting commands remain in $M^{o}$, but there is a conflict, then
$M^{o}$ would be a proper subset of the merger returned by the algorithm,
which is absurd. ∎

###  6.3 Structural properties of the conflict graph

Algorithm 6.2 can be implemented as a graph algorithm working on the bipartite
conflict graph of the disjoint command sets $A$ and $B$ as depicted in Figure
5. At each iteration a “winner” command $\sigma$ is chosen, and all neighbors
of $\sigma$ in the other set are deleted. Building the conflict graph naïvely
requires quadratic time. Structural properties of this graph can be used to
create a more efficient implementation of the synchronization algorithm. Some
of those properties are discussed here.

We call a conflict between two commands _structural_ if the outout types of
the commands are different, and a _content conflict_ otherwise. An example for
a content conflict is when both replicas replace the same directory with
different file contents. The best resolution of a content conflict cannot
necessarily be achieved by the above winner/loser paradigm, as it uses
filesystem-level information only. Fortunately, content conflicts are
represented in the conflict graph as isolated edges. It means that all of
these conflicts must (and can) be resolved independently of all the other
conflicts. We deem it good practice to resolve all content conflicts first.

If $(\sigma,\tau)$ is a conflicting pair and $\sigma^{\prime}\in A$ is on a
node which is above the node of $\sigma$, then $(\sigma^{\prime},\tau)$ is
also a conflicting pair. Proposition 6.1 implies the same when
$\sigma\ll\sigma^{\prime}$. Consequently all elements of a _constructor_
cluster (see Section 4.2) of $A$ are in conflict with exactly the same
elements of $B$, and so the whole constructor cluster can be replaced by a
single graph node, thus reducing the graph size. 5 shows the typical structure
of conflict graphs. Elements of the destructor chain
$\sigma_{5}\ll\sigma_{4}\ll\cdots\ll\sigma_{1}$ are connected to more and more
conflicting commands (this is so as the corresponding nodes go upwards).
Choosing $\tau_{5}$ as a winner automatically resolves all conflicts by wiping
out all $\sigma_{i}$.

Automatic conflict-based synchronizers typically give precedence to
constructors in conflicts between a constructor and a destructor command
syncpal-thesis ; TSR15 , arguing that it is easier to remove some content
again than recreating it. While this is good guidance most of the time, one
has to be aware that in the current framework, replacing a directory node with
some file content is a _destructor_. Confronted with the conflicting
constructor command that creates a file under the same directory, marking this
latter command as the winner is not self-evident.

##  7 Conclusions

We have presented a complete theoretical investigation of filesystem
synchronization. Our definition of a filesystem is arguably simplistic, but it
captures the important features of real-word implementations. The changes
between the original and the updated filesystems are encoded using a sequence
of virtual filesystem commands. The synchronizer receives two sequences
corresponding to the two replicas to be synchronized, and produces a third
sequence which describes the synchronized, or merged state. Definition 5 gives
an intuitively correct and convincing description of when the resulting
sequence leads to a meaningful merged filesystem. In Section 5 we proved an
operational characterization of the possible merged filesystems. The main
result of Section 6 is a conflict-based non-deterministic synchronization
algorithm which creates exactly those merger sequences which are allowed by
Definition 5. The simplicity of this algorithm and the complexity of proving
its correctness was a surprise to us. Its success underlines the power of the
algebraic framework of file synchronization developed in Csi16 .

Multiple questions and possible extensions of the current work remain which
are the subject of future research. Some of them are discussed in the next
subsections.

###  7.1 Synchronizing more than two replicas

The first natural question is to extend the synchronization algorithm from two
to three or more replicas. An encouraging observation is that if several
canonical sets are pairwise refluent (for any pair there is a filesystem on
which both of them work), then they are _jointly refluent_ , meaning that
there is a single filesystem on which all of them work. The natural extension
of Definition 5 for three canonical sets $A$, $B$ and $C$ is to define their
merger as a maximal canonical set $M\subseteq A\cup B\cup C$. This definition
has the additional advantage that it is symmetric in the filesystems, and does
not give precedence to any of them over the others. We can prove that such a
merger also satisfies an operational characterization similar to the one
stated in Theorem 5. It seems that such a 3-way merger can be generated first
by merging $A$ and $B$ to $M$, and then merging $M$ and $C$. Is this claim
true?

Another question is whether the general task of finding a 3-way merger can be
reduced to the case when $A$, $B$ and $C$ are pairwise disjoint. Finally, at
least in the case when the sets $A$, $B$, $C$ are pairwise disjoint, whether
the following variant of the Iteration step of Algorithm 6.2 generates a 3-way
merger, and if yes, whether it generates all possibilities:

Iterate: Pick a winner command $\sigma$ from $A\cup B\cup C$, and discard
those commands from the other two sets which are in conflict with $\sigma$.

###  7.2 Efficiency of the algorithms

Algorithm 6.2 can be implemented with a runtime that increases linearly with
the size of its input, so it is efficient. The trivial running time estimation
of Algorithm 6.2 is proportional to the product of the sizes of the command
sets $A$ and $B$ – assuming that the “above” relation in the node structure
$\mathbb{N}$ can be checked in constant time, as generating the conflict graph
takes that much time. Section 6.3 discusses some possible improvements by
exploiting the structure of the conflict graph. As to whether the running time
of the algorithm can be improved significantly, or it is substantially
quadratic, our conjecture is that the algorithm can be made sub-quadratic.

###  7.3 Attributes

Attributes typically store metainformation about a node, such as different
timestamps (e.g. creation date, last modification or last access) and
permissions (e.g. read and write access), and whether the metainformation
refers to the node only or to the whole subtree below it. Attributes are set
and modified either automatically, or by special filesystem commands. In our
filesystem model attributes can be best modeled by storing them as node
content. For file nodes it means that the attributes are added to the actual
file content, which means that any change to the attributes can be handled as
a change in content. Therefore, file attributes pose no special problems and
can be integrated seamlessly into our model. Handling directory attributes,
however, is a challenging open problem. A general algebraic framework of
filesystems allowing content in directory (and even in empty) nodes was
developed in CC22  at the expense of more complicated notions and theorems.
Unfortunately, with this extension many of the Propositions in Sections 5 and
6 on which the correctness of our method relies do not remain true. To
illustrate the problem, suppose $A$ changes some attribute from “private” to
“public” at some directory node $n$, and creates a file under $n$; while $B$,
under the impression that the directory is still private, creates another file
under it. Then the file creation command from $B$ cannot be unconditionally
moved to the merging sequence.

One possible solution is to consider and resolve all attribute conflicts
(including when $A$ and $B$ modify attributes at the same node differently) as
the first stage of the synchronization process, and then proceed according to
the algorithms described in this paper. This approach, however, is not
necessarily compatible with our declarative Definition 5 of what a
synchronized state is. It is not even clear whether all possible mergers
satisfying this definition are intuitively correct or not if directory
attributes are taken into account.

###  7.4 Links

From the user’s perspective, a _link_ between the nodes $n$ and $n^{\prime}$
is a promise, or a commitment, that the filesystem at and below $n$ is exactly
the same as at and below $n^{\prime}$. Executing a command below $n$
automatically executes the same command on the corresponding node below
$n^{\prime}$. A link system must be _loopless_ meaning that any node has only
finitely many other nodes _equivalent_ to it. In particular, $n$ and
$n^{\prime}$ must be uncomparable nodes.

If the original filesystem $\Phi$ contains links, but the users do not have
tools or permissions to manipulate them, the following synchronization method
works. The update detector, knowing the link structure, unfolds it, and
replaces each user command by the collection of all “hidden” or “implicit”
commands on the equivalent nodes. After creating the canonical command set
$A$, it marks the commands which are on equivalent nodes. For the merger $M$
to be applicable to $\Phi$ it must also contain, with each command in $M$, all
of its equivalents. This can be achieved by the following modification to the
_Iterate_ part of Algorithm 6.2: if $\sigma$ is chosen as a winner, then all
commands equivalent to it will be winners as well.

It is an open problem to introduce filesystem commands which manipulate the
link structure and can be incorporated into our synchronization process.

The research of the second author (L.Cs) has been supported by the GACR
project number 19-04579S and by the Lendulet Program of the HAS, which is
thankfully acknowledged.

Abbreviations The following abbreviations are used in this manuscript:

CRDT | Conflict-free Replicated Data Type
---|---
CSCW | Computer Supported Collaborative Work
OT | Operational Transformation
$\mathbb{O}$, $\mathbb{F}$, $\mathbb{D}$ | empty, file, and directory content
$\Phi$, $\Psi$ | filesystem

References

## References

  * (1) Antkiewicz, M. and Czarnecki, K. Design space of heterogeneous synchronization. In; _Proceedings of GTSE, 2007_ Brava, Portugal. Eds: Lämmek, R. et al, Springer, 2008, pp 3–46.
  * (2) Balasubramaniam, S. and Pierce, B. C. What is a File Synchronizer? In _Proceedings of the 4 th Annual ACM/IEEE International Conference on Mobile Computing and Networking._ New York, NY. ACM, 1998, pp. 98–108.
  * (3) Csirmaz, E.P. Algebraic File Synchronization: Adequacy and Completeness. 2016, arXiv 1601.01736
  * (4) Csirmaz, E.P. and Csirmaz, L. Algebra of Data Reconciliation. _Studia Scientiarium Mathematica Hungarica_ , 2022 DOI: https://doi.org/10.1556/012.2022.01529
  * (5) Day-Richter, J. What’s different about the new Google Docs: Making collaboration fast. Available as https://drive.googleblog.com/2010/09/whats-different-about-new-google-docs.html (accessed at 9 Sep, 2022)
  * (6) Ellis, C.A. and Gibbs, S.J. Concurrency control in groupware systems. In: _Proceedings of SIGMOID conference on Management of data_ , Portland, USA, 1989, ACM, pp. 399–407.
  * (7) Kermarrec, A., Rowstron, A. Shapiro, M. and Druschel, P. The IceCube approach to the reconciliation of divergent replicas. In: _Proceedings of the ACM Symposium on principles of distributed computing 2001_ , Newport, USA, 2001, ACM pp. 210–218
  * (8) Klophaus, R. Riak Core: building distributed applications without shared state. In _SIGPLAN Commercial Users of Functional Programming_ (CUFP ’10). 2010 ACM, NY, USA, Article 14, 1. https://doi.org/10.1145/1900160.1900176
  * (9) Martins, V., Pacitti, E. and Valduriez, P. Distributed semantic reconciliation of replicated data. in _Proc. of CDUR_ , Paris, France. CNAM, 2005, pp. 48–53
  * (10) Ng, A. and Sun, Chengzheng. Operational transformation for real-time synchronization of shared workspace in cloud storage. In: _Proceedings of the 19th International Conference on Supporting Group Work, 2016_ Florida, USA, 2016, ACM pp. 61–70.
  * (11) Nicolaescu, P., Jahns, K., Derntl, M., and Klamma, R. Near real-time peer-to-peer shared editing on extensible data types. In: _Proceedings of the 19th International Conference on Supporting Group Work (GROUP ’16)_ , ACM, pp. 39–49. https://doi.org/10.1145/2957276.2957310
  * (12) Pierce, B.C and and Vouillon, J. What’s in Unison? A Formal Specification and Reference Implementation of a File Synchronizer. _U. of Pennsylvania Technical Reports (CIS) 40_ , 2004\. Available as http://repository.upenn.edu/cis_reports/40
  * (13) Preguiça, N. Conflict-free replicated data types: an overview. 2018, arXiv:1806.10254
  * (14) Preguiça, N., Marques, J. M., Shapiro, M. and Letia, M. A commutative replicated data type for cooperative editing. In: _Proceedings of the 2009 29th International Conference on Distributed Computing Systems_ , Washington DC, ICDS’09, IEEE pp. 395–403
  * (15) Shapiro, M., Preguiça, N., Baquero, C. and Zawirski, M. Conflict-free replicated data types. In: _Stabilization, Safety, and Security of Distributed Systems_ , Springer, 2011, pp. 386–400.
  * (16) Shekow, M. Syncpal: A Simple and Iterative Reconciliation Algorithm for File Synchronizers. PhD Thesis, Aachen University, Germany, 2019
  * (17) Sun, Chengzheng, Jia, X., Zhang, Y., Yang, Y. and Chen, D. Achieving convergence, causality preservation, and intention preservation in real-time cooperative editing systems. _ACM Transactions on Computer-Human Interaction_ 1998 Volume 5 Issue 1 pp. 63–108
  * (18) Sun, Chengzheng and Ellis, C. Operational transformation in real-time group editors. In: _Proceedings of CSCW’98_ , Seattle, USA, 1998, ACM pp 59–68
  * (19) Sun, Chengzheng, Sun, D. Ng, A., Cai, W. and Cho B. Real differences between OT and CRDT under a general transformation framework for consistency maintenance in co-editors. In _Co-Editors. Proc. ACM Hum.-Comput. Interact._ 4, GROUP, Article 06 (January 2020), 26 pages. https://doi.org/10.1145/3375186
  * (20) Tao, V., Shapiro, M. and Rancurel, V. Merging semantics for conflict updates in geo-distributed file systems. In: _Proceedings of SYSTOR’15_ , New Yourk, USA, 2015, ACM pp. 10:1–10:12
  * (21) Terry, D.B. et al. Managing Update Conflicts in Bayou, a Weakly Connected Replicated Storage System. in _Proceedings of the Fifteenth ACM Symposium on Operating Systems Principles._ New York, NY. ACM, 1995, pp. 172–182.