Three-Way Merging Algorithm for Structured Data

Abstract

A general problem in multi-node systems is data synchronization, where the most used method uses synchronous data updating. All changes made by the user are immediately reflected in the data shared with other users. This also means that the user must be constantly connected to the data source via a computer network. As a result, each user always has instant access to up-to-date data. However, the trend in computer systems nowadays is more and more focused on mobility. For this reason, some systems are designed in such a way that it is not necessary or desirable for them to require constant network connectivity. In such systems with asynchronous data updating, it is significantly more complicated to keep the data up to date. The user has all the necessary data available locally on their computer and synchronizes it with the global state of the information system on demand. In this paper, we describe a novel algorithm that can merge data during asynchronous updates. The design of our algorithm is inspired by the diff3 algorithm. Since the diff3 algorithm is designed only for merging text files, we had to change it to enable data merging at the level of programming structures. The proposed algorithm has been verified and implemented in the IS ZONA developed by our department.

Keywords

• Three-way merge
• asynchronous data
• software algorithms
• data integration
• data merging
• algorithm design