Data synchronization

Data synchronization is the process of establishing consistency among data from a source to a target data storage and vice versa and the continuous harmonization of the data over time. It is fundamental to a wide variety of applications, including file synchronization and mobile device synchronization e.g., for PDAs.^[1] ^[2] Synchronization can also be useful in encryption for synchronizing Public Key Servers.^[3]

File-based solutions

There are tools available for file synchronization, version control (CVS, Subversion, etc.), distributed filesystems (Coda, etc.), and mirroring (rsync, etc.), in that all these attempt to keep sets of files synchronized. However, only version control and file synchronization tools can deal with modifications to more than one copy of the files.

File synchronization is commonly used for home backups on external hard drives or updating for transport on USB flash drives. The automatic process prevents copying already identical files, thus can save considerable time relative to a manual copy, also being faster and less error prone.^[4]
Version control tools are intended to deal with situations where more than one user attempts to simultaneously modify the same file, while file synchronizers are optimized for situations where only one copy of the file will be edited at a time. For this reason, although version control tools can be used for file synchronization, dedicated programs require less overhead.
Distributed filesystems may also be seen as ensuring multiple versions of a file are synchronized. This normally requires that the devices storing the files are always connected, but some distributed file systems like Coda allow disconnected operation followed by reconciliation. The merging facilities of a distributed file system are typically more limited than those of a version control system because most file systems do not keep a version graph.
Mirror (computing): A mirror is an exact copy of a data set. On the Internet, a mirror site is an exact copy of another Internet site. Mirror sites are most commonly used to provide multiple sources of the same information, and are of particular value as a way of providing reliable access to large downloads.

Theoretical models

Several theoretical models of data synchronization exist in the research literature, and the problem is also related to the problem of Slepian–Wolf coding in information theory. The models are classified based on how they consider the data to be synchronized.

Unordered data

The problem of synchronizing unordered data (also known as the set reconciliation problem) is modeled as an attempt to compute the symmetric difference $S_{A}\oplus S_{B}=(S_{A}-S_{B})\cup (S_{B}-S_{A})$ between two remote sets $S_{A}$ and $S_{B}$ of b-bit numbers.^[5] Some solutions to this problem are typified by:

Wholesale transfer: In this case all data is transferred to one host for a local comparison.
Timestamp synchronization: In this case all changes to the data are marked with timestamps. Synchronization proceeds by transferring all data with a timestamp later than the previous synchronization.^[6]
Mathematical synchronization: In this case data are treated as mathematical objects and synchronization corresponds to a mathematical process.^[5]^[7]^[8]

Ordered data

In this case, two remote strings $\sigma _{A}$ and $\sigma _{B}$ need to be reconciled. Typically, it is assumed that these strings differ by up to a fixed number of edits (i.e. character insertions, deletions, or modifications). Then data synchronization is the process of reducing edit distance between $\sigma _{A}$ and $\sigma _{B}$ , up to the ideal distance of zero. This is applied in all filesystem based synchronizations (where the data is ordered). Many practical applications of this are discussed or referenced above.

It is sometimes possible to transform the problem to one of unordered data through a process known as shingling (splitting the strings into shingles^{[clarification needed]}).^[9]

Error handling

In fault-tolerant systems, distributed databases must be able to cope with the loss or corruption of (part of) their data. The first step is usually replication, which involves making multiple copies of the data and keeping them all up to date as changes are made. However, it is then necessary to decide which copy to rely on when loss or corruption of an instance occurs.

The simplest approach is to have a single master instance that is the sole source of truth. Changes to it are replicated to other instances, and one of those instances becomes the new master when the old master fails.

Paxos and Raft are more complex protocols that exist to solve problems with transient effects during failover, such as two instances thinking they are the master at the same time.

Secret sharing is useful if failures of whole nodes are very common. This moves synchronization from an explicit recovery process to being part of each read, where a read of some data requires retrieving encoded data from several different nodes. If corrupt or out-of-date data may be present on some nodes, this approach may also benefit from the use of an error correction code.

DHTs and Blockchains try to solve the problem of synchronization between many nodes (hundreds to billions).

References

^ Agarwal, S.; Starobinski, D.; Ari Trachtenberg (2002). "On the scalability of data synchronization protocols for PDAs and mobile devices". IEEE Network. 16 (4): 22–28. CiteSeerX 10.1.1.12.5572. doi:10.1109/MNET.2002.1020232.
^ S. Braun; R. Carbon; M. Naab (2016). "Piloting a Mobile-App Ecosystem for Smart Farming". IEEE Software. 33 (4): 9–14. doi:10.1109/MS.2016.98.
^ "sks.dnsalias.net". Archived from the original on 2007-03-05. Retrieved 2019-07-17.
^ A. Tridgell (February 1999). "Efficient algorithms for sorting and synchronization" (PDF). PhD thesis. The Australian National University. {{cite journal}}: Cite journal requires |journal= (help)
^ ^a ^b Minsky, Y.; Ari Trachtenberg; Zippel, R. (2003). "Set reconciliation with nearly optimal communication complexity". IEEE Transactions on Information Theory. 49 (9): 2213–2218. CiteSeerX 10.1.1.73.5806. doi:10.1109/TIT.2003.815784.
^ "Palm developer knowledgebase manuals". Archived from the original on 2002-03-11. Retrieved 2007-01-09.
^ Ari Trachtenberg; D. Starobinski; S. Agarwal. "Fast PDA Synchronization Using Characteristic Polynomial Interpolation" (PDF). IEEE INFOCOM 2002. doi:10.1109/INFCOM.2002.1019402.
^ Y. Minsky and A. Trachtenberg, Scalable set reconciliation, Allerton Conference on Communication, Control, and Computing, Oct. 2002
^ S. Agarwal; V. Chauhan; Ari Trachtenberg (November 2006). "Bandwidth efficient string reconciliation using puzzles" (PDF). IEEE Transactions on Parallel and Distributed Systems. 17 (11): 1217–1225. doi:10.1109/TPDS.2006.148. Retrieved 2007-05-23.

[Agarwal2002-1] Agarwal, S.; Starobinski, D.; Ari Trachtenberg (2002). "On the scalability of data synchronization protocols for PDAs and mobile devices". IEEE Network. 16 (4): 22–28. CiteSeerX 10.1.1.12.5572. doi:10.1109/MNET.2002.1020232.

[ieeesw1-2] S. Braun; R. Carbon; M. Naab (2016). "Piloting a Mobile-App Ecosystem for Smart Farming". IEEE Software. 33 (4): 9–14. doi:10.1109/MS.2016.98.

[3] "sks.dnsalias.net". Archived from the original on 2007-03-05. Retrieved 2019-07-17.

[4] A. Tridgell (February 1999). "Efficient algorithms for sorting and synchronization" (PDF). PhD thesis. The Australian National University. {{cite journal}}: Cite journal requires |journal= (help)

[minksy-trachtenberg-zippel-5] Minsky, Y.; Ari Trachtenberg; Zippel, R. (2003). "Set reconciliation with nearly optimal communication complexity". IEEE Transactions on Information Theory. 49 (9): 2213–2218. CiteSeerX 10.1.1.73.5806. doi:10.1109/TIT.2003.815784.

[6] "Palm developer knowledgebase manuals". Archived from the original on 2002-03-11. Retrieved 2007-01-09.

[7] Ari Trachtenberg; D. Starobinski; S. Agarwal. "Fast PDA Synchronization Using Characteristic Polynomial Interpolation" (PDF). IEEE INFOCOM 2002. doi:10.1109/INFCOM.2002.1019402.

[8] Y. Minsky and A. Trachtenberg, Scalable set reconciliation, Allerton Conference on Communication, Control, and Computing, Oct. 2002

[9] S. Agarwal; V. Chauhan; Ari Trachtenberg (November 2006). "Bandwidth efficient string reconciliation using puzzles" (PDF). IEEE Transactions on Parallel and Distributed Systems. 17 (11): 1217–1225. doi:10.1109/TPDS.2006.148. Retrieved 2007-05-23.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]