Replication and inconsistency management in XMIDDLE

This material is extracted from Mirco Musolesi's Master degree thesis.

 

 

Since the service that our middleware provides is data sharing, the most important aspects of XMIDDLE are data replication and synchronization. Inconsistency management of distributed replicated data is an open and complex research area; also recently a great number of systems and innovative approaches have been presented. XMIDDLE manages trees that are classic but, at the same time, very expressive data structures, described by means of XML documents. In this chapter we will analyse in details these issues, discussing existing related works, showing our original solutions and pointing out the advantages of our approach.

 

 

Replication and data consistency

 

Concepts and models

A fundamental issue in distributed systems is data replication [CouDK01], since it is a widely used technique to enhance service provision in several application scenarios.  For example, data may be replicated in order to share workload or to increase availability, especially in a mobile context, where disconnections are probable and, in some cases, frequent.

In fact, if we do not consider delays due to pessimistic concurrency control conflicts (i.e., data locking), the factors that are relevant to high data availability are server failures, network partitions and unexpected disconnections. On the other hand, distributed data are not necessarily consistent, because, for instance, they may be out of date: for this reason, disconnected operations are only feasible if users (or applications) can cope with stale data and can resolve any conflicts that arise.

A common requirement is replication transparency; in other words, clients should not have to be aware that multiple copies of data exist. This is not only the possible solution; in fact we can also find examples of systems in which the user can decide the replication strategy and the reconciliation policy.

Considering for example an object-oriented context, we can define two possible models: the first possibility is that objects are replication-aware; the second approach is based on using middleware for replica management (this is the case of XMIDDLE); the following figure summarises these general patterns.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 


 (a) A distributed system for replication-aware distributed objects. (b) Middleware system responsible for replica management

 

Middleware systems for data sharing hide the complexity related to inconsistency management allowing developers to build applications without having to deal with this challenging issue.

 

 

Possible approaches to the problem of inconsistency management of distributed data replicas

In Chapter 2 we have analysed examples of data sharing in some existing middleware platforms and we have pointed out how the problem of inconsistency of replicated data is tackled. Now we discuss some systems that do not belong to this class, examining other interesting approaches to this problem; then, we will present the solution that we have adopted in XMIDDLE.

 

Lotus Notes

Lotus Notes [Lot00] is a database-oriented system firstly developed by Lotus Development Corporation and now handled by IBM, which bought Lotus at the end of the 1990s. The model of this system is client-server; it is composed of three types of components: clients, servers, databases (that are associated locally both to a client and to a server); the key elements are notes, which form the local databases.

Lotus Notes, like Bayou, uses pair-wise reconciliation between replicas. It detects conflicting updates to a document using timestamps but it does not provide a support for application-specific conflict resolution, because the synchronization policies are hard-wired: for instance, an update/delete conflict always gives priority to the delete operation. In some cases, after various attempts, Lotus cannot solve the conflict and manual intervention is needed: however, the system chooses a “winning document”, demoting the other documents as “losers” but maintains them so the user can decide to change the default resolution.

 

CVS

CVS [Ced02] is a source code versioning tool largely used in the software engineering community; developers manage their own replicas and a repository holds the master copy of each file. Programmers manage the coherence of the different versions; when they want to synchronise with the repository, they retrieve the master copy and try to integrate their modifications. The CVS conflict resolution is similar to the “Copy-Modify-Merge” technique included in the Sun Network Software Environment (NSE) [Cou89]. This paradigm enables concurrent collaborative work; after copying data (usually source code), users can work disconnected and modify local replicas. During this stage, divergences between copies can occur; thus, in order to reach a consistent state again, developers have to re-synchronize with the master copy, without overwriting concurrent changes.

CVS detects conflicts, but it is the user that resolves them. We also point out that this detection process is purely based on textual comparison and always needs the intervention of the user; in fact, it simply prepares a list of conflicts with the indication of their position in the file.

 

IceCube

IceCube [KerRSD01] [ShaRK00] is a project developed at Cambridge Microsoft Research Centre concerning the problem of the reconciliation of divergent data replicas. It is a log-based system: the input to the reconciler component is a common initial state and the logs of actions that were performed on each replica; in other words, these represent the history of user actions. IceCube provides programmers with a parameterisable framework for reconciliation; developers can influence this process, either by providing local semantic information (in the form of pre-conditions and post-conditions) or using a global policy.

According to the IceCube model, there are two possible states for an application: isolated execution and reconciliation phase. In the first one, it operates on a local replica of shared objects, which are called the object universe; the operations are recorded in a local log, as ordered set of actions. During the second phase, the logs of two or more replicas are merged to bring the replicas to a consistent state.

The reconciliation phase is composed of three stages:

-         scheduling stage, during which the logs are merged and a new log is produced; from this, a certain number of possible schedules are deduced;

-         simulation stage, during which the schedules are tested to verify the constraints; a schedule that does not satisfy a constraint is aborted;

-         selection stage, during which the application decides among the possible schedules after a ranking operation.

To sum up briefly, IceCube provides applications with powerful and efficient mechanisms, addressing the problem of the inconsistency management.

 

SynchML

SynchML [Syn02] is an industry initiative (supported, among others, by Ericsson, IBM, Motorola, Nokia, Palm and Psion) to develop and promote a single, common data synchronization protocol.  It targets all networks, both wireless and wired, and supports multiple transport protocols, including HTTP, WSP (Wireless Session Protocol), OBEX (Bluetooth, IrDA), SMTP, TCP/IP and some common personal data formats such as vCard or vCalendar.

The programming framework is based on two client-server protocols, SyncML Representation protocol and SyncML Synchronization protocol; the first defines the representation format of SyncML messages (in XML) and details the inner workings of the framework, while the second describes the actions between a SyncML client and a SyncML server. The specification of this standard requires that both client and server maintain information about changes or modification to the data (for example, replacement, addition or deletion) in their databases by a mechanism called change log. In SynchML a version conflict happens when a single data item is modified on both the client and the server databases.

To operate in environments with limited bandwidth, SyncML utilizes WAP Binary XML (WBXML) [OMA02] to keep the data packets as small as possible. It also tries to reduce the number of request-response interactions between devices in order to minimize transmission costs.

For the reconciliation of divergent copies, servers (but also clients can have a restricted number of functionalities of this type) use a so-called synch engine, which adopts some pre-defined status codes for the notification of the chosen conflict resolution policy to the other hosts. Here are some examples of these:

-         207: Conflict resolved with data merge

-         208: Conflict resolved with client "win"

-         209: Conflict resolved with data duplication

To support context-awareness, SyncML also enables clients and servers to exchange information about their respective capabilities during an initialisation phase; either device can request this before a synchronization session. Since SynchML provides a synchronization model based on a client-server protocol, it is not suitable for an ad-hoc environment.

We can also point out that Microsoft does not participate in this initiative:

Since it holds a significant market-share with its proprietary operating system (Pocket PC) and solutions for back-end databases (SQL Server), it instead developed the ActiveSync software [Mic02], a synchronization tool for PocketPC, which is optimized for retrieving data from an SQL Server database.

 

 

Versioning system

Data replication and synchronization are two fundamental aspects of XMIDDLE; we now describe how our system manages different versions of XML documents using DOM and, then, we detail the reconciliation process.

In order to facilitate the automatic detection of conflicts and to support data reconciliation, XMIDDLE uses a versioning system.

The principal structure maintained on every host is a tree that contains a directed version graph of the data elements generated by the hosts that forms the ad-hoc network. There are two types of elements: versions and editions. Versions contain changes that have been performed locally (without communicating them to the other hosts). Editions are, in a sense, stable versions; they contain changes that have been agreed with another host, after a reconciliation process.

We refer to the process of establishing a new edition as releasing a version. Moreover, an edition can be saved to a persistent storage medium, such as Flash RAM, whereas a version is still subject to changes and it is only kept in main memory. Therefore, an edition can have both versions and editions as directed descendents in the version graph, whereas a version does not have descendants, because first it has to be turned into an edition. Consequently, versions always contain the most recent information. The following figure shows these concepts in the case of three different hosts. In this illustration, HostA and HostC have released two editions of the tree and, currently, HostA works on a modified copy (a version) of the latest common edition (marked with number 2). HostB has only a version (it has not reconciled it with other hosts).

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 


Version history graph of DOM trees

 

Shared elements are distinguished by an edition identifier, which uniquely identifies an edition. The identifier is a tuple, like

 

EdID (editionNumber, Hi, Hj)

 

In this expression, Hi and Hj identify the two hosts that agreed in releasing this edition and editionNumber is the maximum of the two previous edition numbers incremented by one. This is used to distinguish between subsequent editions agreed by the same couple of hosts. We also assume that the sequence of edition numbers always starts from number one, when the element is first exported by the owning host. When a version is derived from an edition, a letter “v” is appended to the edition number. Moreover, we use the symbol $ when the creation of the edition does not involve a second host (for example, this is the case of a host that generates the first edition after the export operation performed by an application).

This versioning scheme solves the problem of identifying different editions of shared information in a distributed system that lacks a central authority to issue edition numbers; in fact, it is possible for two hosts to reconcile a tree they copied from another host, without interacting with the owner (in our case, a possible central authority). This is a coordination pattern that is suitable for a mobile setting; in other words, we apply a typical peer-to-peer solution, without the presence of a host that is able to provide particular service (in our case, number edition issuing).

Now we may consider an example, which is illustrated in the following figure, with four hosts HA, HB, HC and HD that store edition 1 of a tree T linked from host HX.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 


An example of Edition identifiers in XMIDDLE

 

During a disconnection, they can modify their local version independently from each other; when two hosts get in touch again, for example HA and HB, as showed in the picture, they reconcile their copies, creating a new edition with editionNumber equal to 2. The same may happen to HC and HD with another reconciliation process leading to a different edition 2. In this situation, if HA and HC connect and look at the edition number only, they may erroneously assume their latest common version of T is number 2; the technique adopted in XMIDDLE eliminates the problem. In fact, HA and HC are able to recognize that they have two different versions of the tree, with different labels, respectively   EdId(2,HA,HB) and EdId(2,HC,HD). Therefore, they can reconcile their different editions and generate a new one with editionNumber equal to 2, labelled with EdId (3,HA,HC). We can observe that in the figure two versions are also represented; they can be distinguished by the letter v attached to their edition numbers.

 

 

The XML TreeDiff algorithm

In order to detect changes in its XML tree structure, XMIDDLE uses an algorithm similar to IBM XML TreeDiff [IBM98].

The computational process of differentiating two labelled tree structures is expensive; in fact, for example, its cost for ordered trees is at least quadratic in the number of nodes. A traditional approach to this problem is to use a tree-tree comparison technique, which was first presented by Tai [Tai79].

IBM XMLTreeDiff is based on a technique proposed by Zhang [ZhaS89] to find differences between two generic trees. It uses a two-step process:  firstly it reduces the size of both trees by fast sub-tree matching using the DOMHash technology [MarTU00] developed at the IBM Tokyo Research Laboratory.  Subsequently, Zhang’s optimal editing distance algorithm is applied to the sub-trees. IBM XML TreeDiff is provided as a set of Java Beans, which directly manipulate the DOM representation of XML documents. The output is an XML document as well, where the differences between data tree structures are showed according to a pure object-oriented style, in the form of edit operations (i.e., change a label on a node, insert and delete nodes, and prune and graft sub-trees). It is worth nothing that IBM XML TreeDiff does not use the traditional approach that consists in the indication of line mismatches. 

In XMIDDLE we use a simplified version of this algorithm, which is also suitable for mobile applications, since it is not too heavy as regards memory and computational requirements. In order to understand how it works, we show an example using the same simplified XML documents that we have presented in Chapter 3 to illustrate the data representation in our system. We will then introduce the complete structure of the documents managed in XMIDDLE. We may consider the following two XML documents (DocA and DocB) representing the shopping baskets of two users that we call respectively MemberA and MemberB.

MemberA stores the following data structure:

 

<?xml version=”1.0”?>

<basket>

<item>

                  <name>pen</name>

                  <quantity>1</quantity>

                  <price>1.15</price>

            </item>

<item>

                  <name>lightbulb</name>

                  <quantity>1</quantity>

                  <price>0.9</price>

           </item>

</basket>

 

MemberB’s document is the following:

 

<?xml version=”1.0”?>

<basket>

<item>

                 <name>pen</name>

                 <quantity>2</quantity>

                 <price>1.15</price>

           </item>

</basket>

 

In order to find the differences between DocA and DocB, we use our XML TreeDiff algorithm; before analysing the output returned by this, we notice that, there are two divergences: firstly, the root of DocB has only one child, while the root of DocA has two children; secondly, the values of the text nodes that are children of the quantity node are different.

The output of the XML TreeDiff algorithm, with DocA as first parameter and DocB as second, is the following:

 

<?xml version="1.0"?>

<treediff>

      <changepcdata newvalue="2" oldvalue="1"  xpath="/basket/item[1]/quantity[1]">

   </changepcdata>

   <delsub-tree xpath="/basket/item[2]"></delsubtree>

</treediff>

 

It is worth noting that the operations that are reported in this XML document have to be applied to document DocA in order to obtain DocB. In other words, if we change the order of parameters, the result is different, since the output of this algorithm is not a list of differences, but the operations that must be performed on the first document in order to produce the second. In fact, the result of this algorithm, with DocB as first parameter and DocA as second, is the following:

 

<?xml version="1.0"?>

<treediff>

      <changepcdata newvalue="1" oldvalue="2" xpath="/basket/item[1]/quantity[1]">

      </changepcdata>

      <addsubtree insertOrder="1" xpathleftsibling="/basket/item[1]" xpathparent="/basket">

            <item>

              <name>lightbulb</name>

              <quantity>1</quantity>

              <price>0.18</price>

            </item>

      </addsubtree>

</treediff>

 

This asymmetry has to be considered in the design of the synchronization process; therefore, we underline that, in XMIDDLE, this algorithm is prevalently used to reconstruct the current different trees from a common edition in a host, before starting the reconciliation between them.

 

 

Reconciliation protocol

The reconciliation protocol is one of the most important design aspects of XMIDDLE and, for this reason, we will analyse it in details. Essentially, its aim is to obtain a consistent version of the same tree once two hosts become connected. It is based on DOM tree differentiating and merging techniques (mainly on XML TreeDiff). In fact, the design goals of this protocol are to minimise data transfers, only transmitting the differences between data structures and, at the same time, to be able to reconstruct diverging replicas from a common previous edition on the same host, in order to reconcile them locally. Then, the result of the reconciliation is propagated to the other host, communicating only the changes performed on a common edition.

In order to describe the protocol, we use the following notation:

 

X à msg Y

 

The meaning of this expression is: the message msg has been sent from X to Y.

 

1) HB à LinkedFromB, ExportLinkB HA

When two hosts get in reach, in order to see whether they share some information they exchange their LinkedFrom and ExportLink sets. Firstly, HB sends to HA its LinkedFrom and ExportLink sets.

 

2) HA à LinkedFromA, ExportLinkA HB

Similarly, HB sends to HA its LinkedFrom and ExportLink. If they realize that they are sharing a branch T, they first lock it and then they start the reconciliation process.

 

3) HB à T, ListOfEI HA

HB sends to HA the list of all edition identifiers previously released for T.

 

4) HA à LastSharedEI, ListOfChanges HB

HA parses the list of edition identifiers sent to it and finds the latest shared edition identifier by searching its version graph. Then HA computes the changes performed and sends this list of differences together with lastSharedEI to HB.

 

5) HB à NewChanges,NewEI HA

In order to reconstruct an up-to-date copy of HA’s tree T’, HB applies the differences that it has received. Then it computes the differences between its own latest version and T’ and reconciles these XML tree structures, using the techniques that we will describe later in this chapter to resolve the possible conflicts. The next step is to communicate these changes to the other host; thus, HB computes the differences between the reconciled tree, called T’’, and T’ and sends the list of changes to HA (in the expression we have defined it newChanges), along with the new edition identifier. This has the form (maxversion+1, HA, HB), where maxversion is the maximum of the two previous edition numbers.

 

6) HA à ACK HB

HA computes the up-to-date edition and stores it. It also acknowledges the transfer to HB.

 

7) HA à ACK HB

These last two steps are needed to acknowledge the two hosts that the protocol has been successfully completed; in other words, when HB receives the ACK message from HB, it realize that HA has the new edition of T. If any acknowledgement is not received, the hosts automatically rollback to the state the tree was in before the reconciliation process. The initial lock on the trees is also removed.

We now analyse the possible failures of this algorithm and the relative consequences. In case of a failure before step 5, the reconciliation process simply aborts. Otherwise, if the protocol is stopped between step 5 and 6, a rollback procedure is started by both hosts. If it fails between steps 6 and 7, HA rolls back while HB completes successfully the reconciliation process. This does not cause problems, since they will get in reach again, they will reconcile using the lastSharedEI, because HA does not possess newEI.

We have described the protocol that is executed by two hosts, but it is worth noting that the reconciliation process involves all the hosts that share the same sub-tree. In other words, we may consider the situation of three hosts HA, HB, HC that share the same branch T. If HA, for example, modifies T, it has to reconcile its replica with HB and HC. A related possible future research issue is the design of a group protocol that involves three or more hosts contemporaneously based on the same versioning system (for example, considering the latest common edition shared by all participating hosts).

 

Linking protocol

Now we analyse briefly the linking protocol, since it is strictly related to that which we have just described. In fact, the link operation may be performed as reconciliation between a tree T and an empty one, considered as edition 0 of T. The following are the essential steps of this protocol.

 

1) HB à LinkedFromB, ExportLinkB HA

The first step is exactly the same as in the reconciliation protocol: HB sends to HA its LinkedFrom and ExportLink sets.

 

2) HA à LinkedFromA, ExportLinkA HB

The second step is the same as well: HB sends to HA its LinkedFrom and ExportLink sets.

 

3) HB à T, (0,$,$) HA

HB sends to HA the identifier of the empty edition; we use the notation (0,$,$) to indicate this. It can be considered as a particular case of the third step of the reconciliation protocol; in fact, in this case the list of edition identifiers contains only one entry.

 

4) HA à (1,HA,$),LastEdition,ActiveChanges HB

This is the fundamental step of the linking protocol; when HA receives the tuple (0,$,$), it realizes that HB wishes to link to T and replies with the latest common edition, together with a list of changes previously performed on the local initial empty tree. HB can now store this data structure and apply the changes in order to perform the re-synchronization with HA. We also underline that HA sends the first edition of T to HB who is now able to reconcile with any other hosts linking to the same tree. In fact, all the hosts that are linking to the same branch have at least the first edition in common.

The other phases of the protocol are similar to those that we have presented in the previous paragraph.

 

 

Connections and disconnections

Another interesting issue to discuss is how connections and disconnections are managed in XMIDDLE, considering the issues related to data consistency.

The connection procedure is always performed by an application, by using the connect() method; it is worth noting that a host may be connected but at the same time not in reach, as we have discussed in the previous chapter. The reconciliation process is performed automatically in these cases:

-         considering a host that is initially not connected, after a re-connection, if hosts that share the same sub-tree are in reach;

-         considering a host that is initially connected but not in reach with other hosts which shares the same sub-tree, when it gets in reach again with those;

-         considering a group of hosts that share the same sub-tree and are connected and in reach, when one of these performs a modification on its replica (on-line reconciliation).

The disconnection procedure is started by the application in case of an explicit disconnection, whereas it is performed by the middleware in case of an implicit one. It is very simple: for each version not yet released, the host releases it; afterwards, the versioning process is started and the resulting tree is stored. The edition identifiers that are issued during this procedure have the form (editionNumber, HB, $). In case of explicit disconnections, HB does not have to notify the other nodes about its decision, because the middleware takes care of this aspect, providing the list of the hosts that are currently in reach (we will explain the implementation of this mechanism in the next chapter). In other words, if a host gets disconnected (as a consequence of an explicit operation or if the device is not reachable), the other nodes are automatically aware of this fact and start the same disconnection process. We underline an important aspect of this procedure: if it is started by an application, its result is the complete disconnection of the host from the network; if it is initiated by the middleware, it allows the disconnection from a subset of the hosts forming the ad-hoc network. For example, we may consider the case of three hosts initially in reach; host HA may implicitly disconnect from HB and at the same time it may remain connected with HC. This situation is illustrated in the following figure.

 

 

 

 


    

 

 

 

 

 

Hosts HA, HB, HC are in reach

 

 

 

 

 

 

 

 


Host HA is now implicitly disconnected from host HB

 

 

Conflict resolution

 

Overview

XMIDDLE provides developers with primitives and mechanisms to control the reconciliation process of the possible conflicts between different replicas. In other words, it can be performed in an application-specific way. This feature of our middleware is fundamental for a large class of applications.

It is worth noting that XMIDDLE is a middleware and for this reason it provides mechanisms, but it does not implement any particular policy. From this point of view, it is extremely flexible: in fact, programmers can easily develop complex mobile applications that need data sharing, without considering the problems related to disconnections and possible data inconsistencies, but, at the same time, our middleware is application-aware, that is, its behaviour can be modified by developers according to their requirements.

We also underline that the reconciliation process is transparent to the users: they are not aware of the automatic detection and resolution of the conflicts between the different copies and the system does not need their intervention.

Furthermore, XMIDDLE provides mechanisms to change reconciliation policies dynamically; therefore applications are able to modify them if necessary.

 

The semantic problems in conflict resolution

First of all, it is worth noting that if conflict detection is a syntactic problem, conflict resolution is a typical semantic issue; we can compare our data structures, but we cannot solve conflicts without knowing what they represent.

The design of XMIDDLE must be absolutely independent from any particular application requirement and, at the same time, it has to be able to deal with application dependent conflict resolution.  In other words, our middleware must be application-independent, but at the same time application-aware. This is a typical issue in mobile systems design in general, for example in order to address the problems related to the changes of context (bandwidth, position, etc.) or the scarcity of resources. In fact, as we have discussed in the previous chapters, a key aspect in mobile system research [CapEM01] is how to enable this bi-directional flow of information between middleware and applications.

XMIDDLE uses reflection and metadata in order to enable the middleware to decide transparently how to behave in different situations. Through metadata, we can distinguish two aspects of middleware, the mechanisms that it implements and the policies according to which it works. We exploit this approach using XML technologies; application developers can modify the behaviour of the middleware through a small number of documents that are used to describe data and configure the system and the interaction between applications that are located on different hosts.

In XMIDDLE the central aspect is how to manage the synchronization between replicas; now we detail our solution, starting from the classification of the possible conflicts in tree data structures.  In fact, we underline again that it is possible to describe XML documents as tree structures and vice versa; we will follow this approach in our explanation.

 

Possible conflicts

 

Terminology and general considerations

Trees [Sta99] are one of the most commonly used data structures; a familiar example is Unix file system structure. Now we introduce the terminology widely adopted to describe trees. Firstly, we give some preliminary definitions: a node is a single object within a tree; an edge is a connection between two nodes; a path is a list of nodes connected in order by edges. Therefore, we define a tree as a collection of nodes connected by edges so that there is one and only one path between two nodes. If there is more than one path, the collection of nodes is usually called a graph; if there is not a path between some nodes, the collection is named a forest or a disjoint set of trees.

XML documents can be described as rooted trees; in other words they have a node designated as the top of the tree, called root. It is possible to identify other relationships considering the tree as a genealogical structure; given a node, we call parent the node directly above and child the node that is directly below. A node has one parent and none or more children. We name siblings the children of the same parent and leaf a node with no children.

In the XML documents, for example, text nodes are leaves since they cannot have children; we discuss the essential aspects of the XML language (and its possible tree-like DOM representation [W3C02b]) in Appendix A. We define descendants all the nodes that can be reached by going downward along any path and ancestors all the nodes that can be reached by going upwards along the path to the root.

We frequently number the levels in a rooted tree, starting with 0 for the root node level and increasing downwards.  We call the number of the highest level the height or depth of the tree. In a rooted tree, each node is the root of a sub-tree (or branch) that consists of it and all its descendants. In computer science, many different varieties of trees are used and studied, but we do not present them, because it is beyond the scope of this thesis.

Now we examine a classification that is of primary importance in our system, the discrimination between order and unordered trees. In an ordered tree, the children of each node have a certain order (usually thought of as going from left to right). In an unordered tree, the children have no order; we can try to visualize this as a 3-D tree where the children float around under the parent. An unordered tree can be represented with many different ordered trees. For this reason, finding out whether two ordered trees represent the same unordered tree is difficult (this issue is known as the tree-isomorphism problem).

 

 

 

 


 

Different ordered tree representing the same unordered tree

 

In XMIDDLE we apply this definition in a particular way, considering macro-elements with a predefined ordered structure that we call branches; in other words, in an XMIDDLE unordered tree, branches (considering monolithically not only the direct children of the root, but all the levels below) has no order. In other words, the term unordered is referred to the sub-trees rather than single nodes. This is very useful in a great number of applications, where the “logical units” are entire sub-trees and not only the children of a node. For this reason we need a mechanism to describe branches; we will describe this interesting aspect later.

We can also motivate our design choices, using XML documents; we may consider the example of the shopping basket, where the “logical units” are the items; the position in the structure (the “item sub-tree”) that is used to describe the products in the tree it is not important. Let us consider, for example the following two documents:

 

 

<?xml version=”1.0”?>

<basket>

<item>

   <name>pen</name>

               <quantity>1</quantity>

               <price>1.15</price>

            </item>

<item>

              <name>rubber</name>

              <quantity>1</quantity>

              <price>0.5</price>

            </item>

</basket>

 

DocA

<?xml version=”1.0”?>

<basket>

       <item>

          <name>rubber</name>

          <quantity>1</quantity>

          <price>0.5</price>

      </item>

      <item>

          <name>pen</name>

          <quantity>1</quantity>

          <price>1.15</price>

      </item>

</basket>

 

DocB

 

We point out that the structure of these documents represents the same contents of the shopping basket, even if the position of the item sub-trees is different.

At the same time, if we want to compare two items, we have to consider the corresponding branches, which are ordered sub-trees. In other words, in order to detect a conflict in leaves we have to compare the values that are in the same position considering the structure of that particular branch (i.e., in an ordered item sub-tree, the children of a quantity node). Let us consider two XML documents, which we denominate respectively DocA and DocB. The first is the following:

 

<?xml version=”1.0”?>

<basket>

<item>

      <name>pen</name>

                  <quantity>1</quantity>

                  <price>1.15</price>

           </item>

</basket>

 

DocB is the following:

 

<?xml version=”1.0”?>

<basket>

        <item>

              <name>rubber</name>

              <quantity>1</quantity>

              <price>0.5</price>

       </item>

</basket>

 

We notice that during the reconciliation of these documents, we find two conflicts: the value of text node that is child of the name node and the values of text node that is child of the price node. In an application like that we have presented, a logical resolution of the conflict is the duplication of the item sub-tree; so we have to deal with another problem, because we must describe the sub-tree that has to be replicated. In fact, conflict detection mechanism provides only the position of the conflicts (in our case we have two changePCData commands with new and old values) and it does not specify how to solve it. Moreover, we cannot simply duplicate the parent node with two different text nodes as children; the next example shows the wrong resolution of the conflict in the node that is child of name node.

 

<?xml version=”1.0”?>

<basket>

<item>

                  <name>rubber</name>

                  <name>pen</name>

                  <quantity>1</quantity>

                  <price>0.5</price>

          </item>

</basket>

 

The logical (and correct) output of the reconciliation process in this case is a basket with two item branches, one from DocA and one from DocB:

 

<?xml version=”1.0”?>

<basket>

<item>

                  <name>pen</name>

                  <quantity>1</quantity>

                  <price>1.15</price>

            </item>

<item>

                  <name>rubber</name>

                  <quantity>1</quantity>

                  <price>0.5</price>

           </item>

</basket>

 

Later we will describe our technique that we use to address this issue. It is worth noting that duplication is not the solution to all these types of conflicts. We may consider, for example, two customers that buy the same product in different quantities. The following XML documents describe their shopping basket:

 

<?xml version=”1.0”?>

<basket>

<item>

                 <name>pen</name>

                 <quantity>1</quantity>

                 <price>1.15</price>

           </item>

</basket>

 

<?xml version=”1.0”?>

<basket>

<item>

                  <name>pen</name>

                  <quantity>2</quantity>

                  <price>1.15</price>

            </item>

</basket>

 

In this case we have a conflict in the text node that is the child of the quantity node; now we should not use the duplication of the branches to solve it, but only choose a new value. Moreover, we need to express a particular policy in order to reconcile it (for example “the greater value must be choosen”, or more complex policy considering also the latest common edition).

Furthermore in other cases the topology of the data structure is fixed and we cannot modify it. Let us consider a tree representing the medallists of an Olympic competition.

 

<?xml version=”1.0”?>

<medallists competition=”100m”>

<goldMedallist>

<name>George Johnson</name>

<nationality>USA</nationality>

<result>9.94</result>

</goldMedallist>

<silverMedallist>

<name>Mark Lewis</name>

<nationality>USA</nationality>

<result>9.98</result>

</silverMedallist>

<bronzeMedallist>

<name>Paul Smith</name>

                        <nationality>UK</nationality>

<result>10.01</result>

</bronzeMedallist>

<medallists>

 

In this case, the topology of the tree is fixed and, for this reason, the detection and the resolution of the conflicts is easier, because we only have to compare the values in the same positions (for example, two timing stations running XMIDDLE may sense two different results for the second athlete and they need to reconcile this conflict); thus, this is a typical example of an ordered tree.

 

Value and structure conflicts

In the previous example we have analysed value conflicts, which are related to the value of text node. The other possible case of this kind of conflicts is related to attribute nodes that contain different strings. For example, we may use an attribute to indicate the availability of a product in a XML document representing a shop catalogue and different replicas may present stale values that need to be reconciled.

During the reconciliation process we can also detect structure conflicts, related to the topology of the tree. A possible example of structure conflict is the following:

 

<?xml version=”1.0”?>

<basket>

<item>

                 <name>pen</name>

                 <quantity>1</quantity>

                 <price>1.15</price>

            </item>

<item>

                 <name>rubber</name>

                 <quantity>1</quantity>

                 <price>0.5</price>

           </item>

</basket>

 

<?xml version=”1.0”?>

<basket>

<item>

     <name>pen</name>

                 <quantity>1</quantity>

                 <price>1.15</price>

            </item>

</basket>

 

We can notice that the difference between these two documents is the number of the children of the root element; in general, a structure conflict arises when we have different relationships among the nodes of the tree. In this case a possible resolution of the conflict is the addition of the sub-tree describing the item rubber.

We may also have a combination of structure and value conflicts, in ordered and unordered trees; we may analyse these documents:

 

<?xml version=”1.0”?>

<basket>

<item>

                  <name>rubber</name>

                  <quantity>1</quantity>

                  <price>0.5</price>

            </item>

<item>

                  <name>pen</name>

                  <quantity>1</quantity>

                  <price>1.15</price>

            </item>

</basket>

 

<?xml version=”1.0”?>

<basket>

<item>

                  <name>pen</name>

                  <quantity>1</quantity>

                  <price>1.15</price>

            </item>

</basket>

 

In this case, the conflict detection mechanism (by using XML TreeDiff algorithm) finds both structure and value conflicts; this is a typical case of an unordered tree; in order to reconcile these documents, we cannot simply compare the values in the same position, but we have to consider the branches and confront them. This is quite difficult, because, for example, two sub-trees describing the same product may have different values in the quantity text node. In this case we have to compare the “pen” sub-tree with the others that are present in the first document, without considering the quantities.

Furthermore, in order to solve a conflict like the one we have just described, it is not sufficient to consider the two documents that have to be reconciled, but we also need to analyse the latest common edition. For example, the addition of the item rubber may lead to a wrong reconciliation; let us suppose that, after a synchronization, the two customers had both products (rubber and pen) in their basket and then the second customer cancelled the purchase of the rubber obtaining these documents. In this case, probably, the better resolution of the conflict is not the addition of the rubber sub-tree in the second document, but its deletion from the first. As you can see from this example, it may be fundamental to consider the common latest edition in the reconciliation process.

Furthermore, it is worth noting that in our system conflicts related to the names of elements (in other words, the name property of a node object) are not possible, because the structure of the documents must be predefined; in other words developers must describe them by using XML Schema and they might also validate them. A determinate element can be found only in specific levels of the tree; moreover, we underline that the approach of the XML TreeDiff algorithm is level-based and it is not possible to detect conflicts related to positions in different levels of the tree. In fact, the comparison between two trees starts from the root element, considering the differences at each level and, on the other hand, the structure of sub-trees is reconstructed by using the XML Schema description of the document that is hierarchical.

In the previous examples we have presented possible ways to solve conflicts that we have adopted as default policies of XMIDDLE.

Moreover, our middleware also offers a non-standard resolution mechanism; this allows developers to specify particular policies in order to solve value conflicts. They can do it by following a very simple procedure by using the attribute resolutor in the element that is the parent of the text node that needs to be managed in a non-standard manner, as you can see in this example from the collaborative shopping case study:

 

<?xml version=”1.0”?>

<basket>

<item>

                  <name>pen</name>

                  <quantity resolutor=”greater”>1</quantity>

                  <price>1.15</price>

            </item>

</basket>

 

When programmers specify the value of this attribute, the middleware solves the conflict related to this element using the suggested policy. For instance we may consider this other document.

 

<?xml version=”1.0”?>

<basket>

<item>

                  <name>pen</name>

                  <quantity resolutor=”greater”>5</quantity>

                  <price>1.15</price>

            </item>

</basket>

 

The reconciled document in this case will be the following:

 

<?xml version=”1.0”?>

<basket>

<item>

                  <name>pen</name>

                  <quantity resolutor=”greater”>5</quantity>

                  <price>1.15</price>

            </item>

</basket>

 

We observe that in this simple case the middleware chooses the greater value according the specified policy.

XMIDDLE provides efficient solutions to address all these issues implementing a standard conflict resolution process that can be easily modified by using application-dependent policies. In the next paragraphs we detail these mechanisms provided by our middleware.

 

Standard conflict resolution

In the previous chapter we have described some common cases, considering data structures from possible applications based on XMIDDLE. Now we introduce and analyse the mechanisms and the solutions that allow our middleware to address the problem of the transparent reconciliation of different replicas with great flexibility. The reconciliation process in XMIDDLE involves three data structures: the two documents that have to be reconciled and their latest common edition; in fact, as we have discussed before, all the hosts that are linking to the same branch have at least the first edition in common.

As we have discussed before, it is necessary to distinguish, according to our definitions, between ordered and unordered data structures. In order to identify the type of tree, developers must use an attribute in the root element called order. This attribute can assume two values, yes or no; if it is not present the middleware assumes that the order is important. A possible example is the following:

 

<?xml version=”1.0”?>

<basket order=”no”>

<item>

                  <name>pen</name>

                  <quantity>1</quantity>

                  <price>1.15</price>

            </item>

<item>

                  <name>rubber</name>

                  <quantity>1</quantity>

                  <price>0.5</price>

           </item>

</basket>

 

Evidently, the reconciliation processes for an ordered and unordered trees are quite different; now we start analysing the case of an ordered tree.

 

Conflict resolution in an ordered tree

We will discuss the reconciliation process for ordered trees analysing the cases of the conflict resolution of value and structure conflicts separately.

In order to analyse the resolution of value conflicts, we consider the following two documents describing for example a colour image, which can be represented with an array of pixels using the RGB format. In this case, the order (from left to right) in the tree is important, since it represents the position in the array of pixels. We present a simplified document with only four pixels. For example, we may consider the following two documents:

 

<?xml version=”1.0”?>

<image order=”yes”>

 <pixel>

                        <R>0</R>

<G>0</G>

<B>0</B>

 </pixel>

 <pixel>

                        <R>0</R>

<G>0</G>

<B>255</B>

 </pixel>

 <pixel>

                        <R>255</R>

<G>255</G>

<B>255</B>

 </pixel>

 <pixel>

                        <R>0</R>

<G>0</G>

<B>0</B>

 </pixel>

</image>

 

DocA

<?xml version=”1.0”?>

<image order=”yes”>

 <pixel>

                        <R>0</R>

<G>0</G>

<B>0</B>

 </pixel>

 <pixel>

                        <R>0</R>

<G>0</G>

<B>255</B>

 </pixel>

 <pixel>

                        <R>255</R>

<G>255</G>

<B>255</B>

 </pixel>

 <pixel>

                        <R>255</R>

<G>255</G>

<B>255</B>

 </pixel>

</image>

 

DocB

 

We notice that the differences in these documents are related to the fourth pixel; in order to reconcile them we have to compare them with the latest common edition. Otherwise, the choice of the “winning document” (using a Lotus Notes terminology) would be arbitrary. By this approach we utilise the common history of the documents in order to decide how to solve the conflict.

For example let us assume that the latest common edition is the following:

 

<?xml version=”1.0”?>

<image order=”yes”>

 <pixel>

                        <R>0</R>

<G>0</G>

<B>0</B>

 </pixel>

 <pixel>

                        <R>0</R>

<G>0</G>

<B>255</B>

 </pixel>

 <pixel>

                        <R>255</R>

<G>255</G>

<B>255</B>

 </pixel>

 <pixel>

                        <R>0</R>

<G>0</G>

<B>0</B>

 </pixel>

</image>

             Docold

 

In this case XMIDDLE chooses the values that are present in DocB, because these are different from those that are contained (in the same positions) in DocOld and, at the same time, the values of DocA are equal to those in DocOld. In other words, after the last reconciliation process, HostB has modified his replica and so we can consider the copy stored in HostA as stale. In the symmetric case (DocB is a stale copy) the middleware chooses the values that are present in DocA.

The case of different values (in the same positions) in all the three documents is the most problematic, because we are not able to make a decision; we implement different behaviours in the prototype of our system: it is possible to opt for a random choice between the two values or to introduce a priority, expressed by a number in the root of the document (if the numbers are equal, we decide randomly between the values of the two copies).

We summarize these concepts in the following table using three different letters (a, b, c) to indicate different values in the same position.

 

Value in DocA

Value in DocB

Value in Common Latest Edition

Choosen value

A

b

a

b

A

b

b

a

A

b

c

a or b

(priority-based or random choice)

 

Resolution of value conflicts in an ordered tree

 

Now we analyse the case of the structure conflicts; as discussed before the “logical unit” in XMIDDLE is a branch; for this reason, we do not use a particular XML structure to describe how the reconciliation works, but generic tree diagrams. First of all, it is worth noting that we adopt the same approach used for value conflicts, exploiting the opportunity of comparing the different copies with the latest common edition.

We will study a simple case with a tree with sub-trees that are directly children of the root node; more complex structures are managed in the same way. Let us consider the following two diagrams representing DocA (replica in HostA) and DocB (replica in HostB) that are showed in the following figure.

 

 


 

 

 

 

 

Structure conflict reconciliation in an ordered tree (example 1)

 

In order to reconcile these two data structures, we consider the latest common edition. We notice that in DocB there is not a sub-tree that is present in both DocA and in the common reconciled document: probably this is the result of the deletion of this branch performed by the application running on HostB, after the last reconciliation process. Therefore, the middleware chooses the structure of DocB, deleting branch Y from DocA. Let us consider another situation, represented in the following figure.

 

 

 

 

 

 

 

 


Structure conflict reconciliation in an ordered tree (example 2)

 

In this case branch Y is present in DocA, but not in DocB and in the latest common edition; probably this means that branch Y has been added after the last reconciliation process.  Therefore, in order to solve this conflict, we have to add branch Y in DocB. The symmetric cases are dealt with in similar ways. We can sum up these concepts in this table:

 

 

DocA

DocB

Latest Common Edition

Reconciled document

Sub-tree T present

Sub-tree T

 not present

Sub-tree T present

Sub-tree T

 not present.

Sub-tree T

 not present

Sub-tree T present

Sub-tree T present

Sub-tree T

 not present

Sub-tree T present

Sub-tree T

not present

Sub-tree T

 not present

Sub-tree T present

Sub-tree T

Not present

Sub-tree T present

Sub-tree T

 not present

Sub-tree T present

 

Resolution of structure conflicts in an ordered tree

 

Conflict resolution in an unordered tree

The conflict resolution in an unordered tree is more complex, since we need to compare elements (and sub-trees) that may be in different positions in the tree structure.

First of all, we study the resolution of value conflicts in these data structures. It is worth noticing that, in this case, the process chooses a document as base and performs the change on this in order to obtain the reconciled document. For example, we can consider these two documents (for the moment, we assume that the two hosts has only an empty edition in common) with DocA as “base document”:

 

<?xml version=”1.0”?>

<basket order=”no”>

  <item>

    <name>pen</name>

    <quantity>1</quantity>

    <price>1.15</price>

  </item>

</basket>

 

DocA

<?xml version=”1.0”?>

<basket order=”no”>

  <item>

    <name>pencil</name>

    <quantity>4</quantity>

    <price>0.75</price>

  </item>

</basket>

 

DocB

 

The middleware detects three value conflicts in this document (the name of the product, its quantity and its price); the order of sub-tree in this case is not important, since from an application point of view it is not relevant (the items may be purchased in a different sequence). For this reason, the correct way to perform the reconciliation is to generate a document with two items, pen and pencil; in other words we have to duplicate the item structure.

XMIDDLE exploits the expressiveness of XML Schema in order to identify the structure of sub-trees correctly. This process is composed of the following steps: the middleware detects the value conflict (for example pen and pencil in the same positions) and reconstruct the branch structure in DocB (in this case the item sub-trees) in which the inconsistency occurs. Afterwards, it checks whether the branch that has been identified is present in DocA in any position. If it is not present the middleware adds it to the base document, otherwise DocA is not modified. It is worth noticing that this process is not performed in the case of application-specific resolution (in other words, when a non standard resolutor is specified); we will discuss this aspect later in this chapter.

We underline that XMIDDLE also checks whether it is present in the latest common edition using the same rules that we have examined before, when we have discussed the case of ordered trees. In other words, only if the sub-tree is not present in the base document and in the latest common version, the middleware performs the branch addition. In order to understand this aspect, we will examine an example in detail, analysing each step of the reconciliation process. Let us consider the tree structure represented in the following figure, indicating with different letters sub-trees with inconsistent structures or values. DocA is the base document; in other words, we compare each branch that is present in DocB with those that are present in DocA and in the common latest edition.

 

 

 

 

 

 

 

 

 

 

 

 


Example of the reconciliation process for unordered trees (comparison between sub-trees).

 

Firstly, we consider branch Z, as you can see in the figure. This sub-tree is present in DocA and in the LatestCommonEdition and for this reason it is not added to the base tree.

Afterwards, we consider the branch marked with the letter X; since it is not present in the other two documents, it is added to the base tree. In fact, this is the case of an addition of a sub-tree after the last synchronization.

The reconciliation process is not completed after these two steps; in fact we have to perform the same comparisons with the other tree structure considering DocA: the branch marked with the letter K is not present in the other documents and it is maintained in the base tree; the other sub-tree is not deleted as well, since it is present in DocB and in the last common edition. Furthermore, we underline that a branch has to be deleted from the base tree only if it is present in the last common edition and not in the other document.

We can sum up these concepts using the following table (T is a sub-tree of DocB):

 

Sub-tree T present in base document

Sub-tree present in latest common edition

Operation performed on base document

Yes

No

Delete sub-tree T

 from base document

Yes

Yes

None

No

No

Add sub-tree T

 to base document

No

Yes

None

 

Resolution of structure conflicts in unordered trees.

 

It is worth noticing that this process is extremely optimised, using several techniques, for example to avoid unnecessary comparisons; we will describe its implementation in details in the next chapter. However, the synchronization is quite complex from a computational point of view and introduces a remarkable overhead, especially for large data structures. On the other hand, the reconciliation process takes place only after a modification of the data structure (if the hosts are connected) or a reconnection between two hosts. The frequency of this event is generally tolerable and, anyway, the advantages that derive from this mechanism are noteworthy. Furthermore, we underline that the communication between the hosts is very limited, since the reconciliation process is not based on a complex negotiation phase.

 

The branch structure problem

In the previous paragraph we have presented the XMIDDLE synchronization process for an unordered tree structure that is essentially based on the comparisons between sub-trees; now we discuss the techniques that are used in our middleware to reconstruct the topology of the branches that must be compared, starting from their leaves (in an XML documents, the text nodes).

Our solution is to exploit XML Schema, since it represents the most expressive standard language for the description of XML documents and at the same time it is extremely simple to use. We use it essentially in order to define the maximum number of possible occurrences of a node in a certain level of the data structure that we are considering. In fact, in other words, our goal is to find the root of the sub-tree; this is usually characterised by not having a predefined maximum number of occurrences.

We start considering the leaves of the tree where the value conflict has been detected (more precisely the node that is the parent of this text node). Analysing the corresponding XML Schema document, if the maximum number of occurrences of this element is unbounded, this is the root of the sub-tree. Otherwise, we consider its parent node and we repeat the same test, recursively. Obviously, this is not a general and standard definition of a branch; however, our approach is suitable for a very large class of applications and developers can modify this standard resolution process by using application dependent policies.

Moreover, it is worth noticing that it is sufficient to perform this procedure only once, since it is sufficient to know the root of only one sub-tree to determine the parent node of all branches.

Now we analyse an example of XML Schema, using the collaborative shopping case study; the XML Schema document is the following:

 

<xsd:schema xmlns:xsd="http://www.w3.org/1999/XMLSchema">

 <xsd:element name="basket">

  <xsd:complexType>

   <xsd:element name="item" type="xsd:string" minOccurs="0" maxOccurs="unbounded">

    <xsd:complexType>

     <xsd:element name="name" type="xsd:string"/>

     <xsd:element name="price" type="xsd:decimal"/>

     <xsd:element name="quantity">

      <xsd:complexType base="decimal">

       <xsd:attribute name="resolutor" use="default" value"add"/>

      </xsd:complexType>

     </xsd:element>

    <xsd:complexType>

   </xsd:element>

  </xsd:complexType>

 </xsd:element>

</xsd:schema>

 

In XML Schema you can specify the minimum number of times that an element appears with the minOccurs attribute and the maximum number with the maxOccurs attribute. The default value for minOccurs is 1; if you do not specify a value for maxOccurs, its default value is the value of minOccurs. To indicate that there is no upper bound to the maxOccurs attribute, it must set to the value unbounded.

Developers have to provide only this simple document in order to enable the XMIDDLE sophisticated automatic reconciliation process. This is a process that we call XML Schema document registration. In the next chapters, we will illustrate the guidelines for designing applications based on our middleware and we will also detail this aspect.

 

Application-specific conflict resolution policies

In the previous paragraphs we have analysed the standard reconciliation process that is automatically performed by the middleware and provide the conflict resolution system with the built-in rules that we have discussed before.

XMIDDLE also supports the definition of application-specific policies for the management of data conflicts. This is achieved through the definition of the Resolutor attribute in the elements that have to be treated using a specific resolution strategy. When this attribute is present, the middleware does not apply the standard method to manage the possible inconsistency in this element (more precisely, using a DOM representation of the tree, in the text node that is child of this element), but uses specific procedures. Some examples of available application specific policies for the resolution of conflicts of numerical values are greater, lesser, add, random, and average. In order to understand how this mechanism works, let us consider these following documents:

 

<?xml version=”1.0”?>

<basket order=”no”>

<item>

                  <name>pen</name>

                  <quantity resolutor=”greater”>1</quantity>

                  <price>1.15</price>

            </item>

<item>

                  <name>rubber</name>

                  <quantity resolutor=”greater”>1</quantity>

                  <price>0.5</price>

            </item>

</basket>

 

            DocB

 

 

<?xml version=”1.0”?>

<basket order=”no”>

<item>

                  <name>pen</name>

                  <quantity resolutor=”greater”>2</quantity>

                  <price>1.15</price>

            </item>

</basket>

 

            DocB

 

In this example, we use an application specific policy to solve the possible conflicts in the quantity element. The policy chosen by the developer in this case is greater. In this case, with respect to the structure conflicts and the other value conflicts, the resolution process is performed in the usual manner, but we have to underline that, when the item describing the pen product in the second document is compared to those which are present in the first document (base document), the middleware does not check the values of the text nodes that are children of the quantity node, because of the presence of the resolutor attribute. In other words the middleware considers the two sub-trees in the first and the second document equal and for this reason it does not add another branch to the base document.

However, after the detection of the presence of an “equal” sub-tree in the base document, XMIDDLE analyses the structure of the document and, for each element with a resolutor attribute, it performs the corresponding specific conflict resolution process. In our case, the middleware uses the greater resolutor; according to this, as the name suggests, the greater value is chosen (in our example two). Therefore, the reconciled document is the following:

 

<?xml version=”1.0”?>

<basket order=”no”>

<item>

                  <name>pen</name>

                  <quantity resolutor=”greater”>2</quantity>

                  <price>1.15</price>

            </item>

<item>

                  <name>rubber</name>

                  <quantity resolutor=”greater”>1</quantity>

                  <price>0.5</price>

           </item>

</basket>

 

It is worth noticing that these resolutors also consider the latest common edition to manage the resolution of conflicts; for example, let us examine the following documents:

 

<?xml version=”1.0”?>

<values>

  <value resolutor=”add”>

  2

  </value>

<values>

 

DocA

<?xml version=”1.0”?>

<values>

  <value resolutor=”add”>

  1

  </value>

<values>

 

DocB

 

We assume that these documents have generated the following common latest edition that is used during the reconciliation process.

 

<?xml version=”1.0”?>

<values>

  <value resolutor=”add”>1</value>

<values>

 

   Docold

 

In this case, if we do not consider the common latest edition, the reconciled value for the value element is 3; but it is not correct, because only the value in DocA is different from the latest common edition (it is incremented by 1); for this reason, we use the following simple formula:

 

ReconciledVal=(valA-valLatestCommonEdition)+(valB-valLatestCommonEdition)

 

If the result is negative we set the value to 0; for example, this is the case with these values: valA=0, valB=0 and valLatestCommonEdition=1.

Therefore, in our example the reconciled document will be the following:

 

<?xml version=”1.0”?>

<values>

  <value resolutor=”add”>2</value>

<values>

 

Let us consider another example; we analyse the following situation, where apparently there is no conflicts:

 

<?xml version=”1.0”?>

<values>

  <value resolutor=”add”>1</value>

<values>

 

DocA

<?xml version=”1.0”?>

<values>

  <value resolutor=”add”>1</value>

<values>

 

DocB

 

Let us assume that the latest common edition is the following document:

 

<?xml version=”1.0”?>

<values>

  <value resolutor=”add”>0</value>

<values>

 

It is worth noticing that the application specific resolution is performed even if there are no inconsistencies between the two documents, since it is triggered only by the presence of resolutor attributes; this is fundamental in order to obtain a correct synchronization process of the replicas in each host.

In fact, some resolutors, such as add, analysing also the latest common edition can update the values considering the “history” of the document in a correct manner. In this case, for example, HostA and HostB have changed the value from 0 to 1. Only by the observation of these documents we cannot detect any conflict, but the middleware, checking the latest common edition, finds the changes and choices the correct up-to-date value; therefore, the reconciled document will be the following:

 

<?xml version=”1.0”?>

<values>

  <value resolutor=”add”>2</value>

<values>

 

We also underline that it is possible to use these application-specific resolution policies in both ordered and unordered tree structures. It is worth noting that developers can use various types of resolutors in the same document.

 

 

Documentation Main Page

References

 

 

Last update: January 2003 by Mirco Musolesi