Concurrency control and merging in a value-oriented XML Store

Overview

In cooperative work there is a need to have some agreement on what is the present state of the work, a consensus of the value representing the present state (Consensus in this context must not be mistaken as the same problem as the byzantine agreement introduced by Lamport et al. (1982)). For instance, consider a group of people that cooperatively and concurrently writes a document.

In order to obtain consensus between workers or applications, some sort of communication is needed conducted by some systematic rule, a consensus protocol, see Figure \ref{figconssynchron}. To uniform and ease the use of the consensus protocol for the application programmer, an interface to a coordinator implementing the protocol is convenient. The interface specifies how the applications communicate with each other to reach consensus through the coordinator. That is, each application does not know how the global consensus is reached, because it is the responsibility of the coordinator. By doing so the applications are decoupled from the process of reaching consensus.

But when the applications and the coordinator is decoupled they might not at all time have the same view of consensus. This leads to the problem of how the coordinator and applications synchronize their view of consensus. This can be summarized by the following:

• How does the application gain knowledge of that the coordinator has obtained a new consensus state?
• How does the coordinator gain knowledge of that the application has created a new value that it wants to contribute as the consensus state.
• Conflicts might happen; what if the coordinator are reaching a new consensus concurrently with the application contributes with a new value for the consensus?
• Knowing that conflicts can occur it might influence the synchronization if consensus in the coordinator consist of more than one value; known as consistency problems.

This thesis analyzes what operation signatures should comprise the interface of the coordinator to make it as generally applicable as possible for the value-oriented XML Store. Further, the problem of conflict resolving will be analyzed and a solution by merging XML documents stored in the XML Store will be given. Finally, the consistency problem of having more than one value represent the consensus will be analyzed an solved.ments stored in the XML Store will be given. Finally, the consistency problem of having more than one value represent the consensus will be analyzed an solved.

Links

• Plan-X
• Ambus - XPath and Routing XML Store
• Swing Connection
• New Java I/O APIs

Synchronization

Consensus

Concurrency control

• Locking shared files

Merge

• GNU Diff
• imediff2 - An interactive fullscreen 2-way merge tool - With source code
• Guiffy - Advanced Cross-Platform Compare/Merge
• Microsoft XML Diff and Patch 1.0
• Logilab XmlDiff
• diffmk - XML diff tool in Perl
• XyDiff Tools - Detecting changes in XML Documents
• DeltaXML - Change control for XML in XML
• Harmony - XML Synchronization
• 3DM XML diff and merge tool

Related work

• Xode - UML Editor
• OceanStore - Providing Global-Scale Persistent Data
• Scribe - A scalable group communication system

Paper

The most recent version of our thesis is available here.

Source

The most recent version of our source is available here.

People

• Bjørn Elo Petersen (bep_itu.dk)
• Jonas Engedal Andersen (jea_itu.dk)