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.
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.
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 [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 [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.
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.
Last update: January 2003 by Mirco Musolesi