Browse Prior Art Database

A transfer protocol for efficiently synchronizing two hierarchies with built-in journalling capabilities. Disclosure Number: IPCOM000224179D
Publication Date: 2012-Dec-12
Document File: 4 page(s) / 97K

Publishing Venue

The Prior Art Database


This article presents a transfer protocol to synchronize hierarchies between two systems. This protocol incorporates revision history in the protocol itself, while minimizing the amount of data transferred between systems. Instead of transmitting a complete copy of the modified tree every time a part of the tree changes, we transmit only a change list consisting of the changed nodes and all their ancestors up to the rootnode. Each item in the changelist received a new global identifier, and is appended to the current tree representation. Previous versions of the tree can be easily restored by stating the identifier of the rootnode of the version that should be reconstructed and recursively traversing the list of children.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 52% of the total text.

Page 01 of 4

A transfer protocol for efficiently synchronizing two hierarchies with built -in

journalling capabilities.

There are many cases in which two separate systems need to synchronize on a single tree structure, or hierarchically oriented document structure. For example, a server and client need to agree on the same state of an XML document, even though the XML document might be edited on the client. Two obvious solutions for this problem are explicit state transfer, where the entire document structure is transferred between the two systems after every change, and incremental updates, where only a small changed section is transferred in response to a change on either side. The first one is not very efficient, especially if the structures in question are large. The second one is efficient in terms of data transfer but is susceptible to failures of server or client, in which case all updates need to be retransmitted in order to ensure both structures share the same state. It also makes retrieving previous states harder, as every single delta has to be reversed to arrive at a previous state.

    Here, a transfer protocol is proposed which is both efficient in terms of the amount of data transferred and includes all of the modification history in a compressed manner, so we can easily restore previous states. This latter property makes it possible to quickly recover from catastrophic failures and offers a straightforward way to integrate undo and redo into the protocol itself.

    We represent the current state of a hierarchical data structure using three parameters:

    a) An indexed list of nodes in the tree, where each entry represents a node in a specific state/version. Each indexed entry contains the list of children that belong under that particular version of the node.

b) A list of the indices of valid root nodes of the hierarchy.

c) An index into the list of valid root nodes that specifies the current root.

A tree can be reconstructed by starting at any element in b) and recursively

following child indices using a). The current state of the tree is represented by c).

    Whenever a node is changed in the tree structure we do not send the entire tree to the other party. Instead we create a new set of n+1 records that represent the changed node and all of its n ancestors and append this recordset to a). This new set of records will also contain a new rootnode with index x . Index x is appended to list b). Finally the index of the current root in c) is updated to x . The only information transferred in response to an update are the new records appended to a) and the index x for the new rootnode.

This protocol has three core advantages over traditional approaches:

Information transferred is low. Unchanged parts of the tree are not part of the

transmitted message. Increased complexity of the tree does not linearly increase the overhead of updates. Instea...