  With distributed computing and mobile applications, synchronizing diverging
replicas of data structures is a more and more common problem. We use algebraic
methods to reason about filesystem operations, and introduce a simplified
definition of conflicting updates to filesystems. We also define algorithms for
update detection and reconciliation and present rigorous proofs that they not
only work as intended, but also cannot be improved on.
  To achieve this, we introduce a novel, symmetric set of filesystem commands
with higher information content, which removes edge cases and increases the
predictive powers of our algebraic model. We also present a number of generally
useful classes and properties of sequences of commands.
  While these results are often intuitive, providing exact proofs for them is
far from trivial. They contribute to our understanding of this special type of
algebraic model, and toward building more complete algebras of filesystem trees
and extending algebraic approaches to other data storage protocols. They also
form a theoretical basis for specifying and guaranteeing the error-free
operation of applications that implement an algebraic approach to
synchronization.

Distributed, Parallel, and Cluster Computing;Discrete Mathematics;Data Structures and Algorithms