Efficient synchronization of two instances of an ordered list

Question

What data structure or algorithm can be used to efficiently synchronize two nearly identical ordered lists? Two offline systems start with the same ordered list and each edit, insert, delete and move items in the list. Occasionally they will be online to synchronize the list. The algorithm should minimize the amount of changed items or "diffs" that need to be communicated.

For an unordered list we would simply use a modification timestamp and UUID for each item to detect edits respectively inserts/deletions. But what data structure can we use for an ordered list? Using an integer rank would require renumbering all successors after an insert, and thus result in many "diffs" when comparing items in both lists. Using a floating-point rank (having the average of the predecessor and successor ranks) would have accuracy problems after inserting many new items.

Using a doubly linked list (i.e. referencing the UUID of the predecessor and successor item) would result in two changed items and one new item for each insert, thus 3 "diffs" when comparing items in both lists.

Any suggestions, pointers to literature or Google search terms about this subject?

Answer 1

For synchronizing from a master list to a slave list, it looks like a fellow named Michael Heyeck has a good, O(n) solution to this problem. Check out that blog post for an explanation and some code. Perhaps this is a good starting point to generalize to a two-way sync.

Essentially, the solution tracks both the master and slave lists in a single pass, tracking indices into each. Two data structures are then managed: a list of insertions to be replayed on the slave list, and a list of deletions.

It looks straightforward and also has the benefit of a proof of minimalism, which Heyeck followed up with in a subsequent post. The code snippet in this post is more compact, as well:

def sync_ordered_list(a, b):
x = 0; y = 0; i = []; d = []
while (x < len(a)) or (y < len(b)):
    if y >= len(b): d.append(x); x += 1
    elif x >= len(a): i.append((y, b[y])); y += 1
    elif a[x] < b[y]: d.append(x); x += 1
    elif a[x] > b[y]: i.append((y, b[y])); y += 1
    else: x += 1; y += 1
return (i,d)

Again, credit to Michael Heyeck.

Answer 2

The standard approach is probably going to be something like this:

• Each side keeps track of the last-synchronized state of the list. In other words, at any point in time, each side knows the state $L_{t-1}$ of the list at the last synchronization point when they synchronized their lists.

• If Alice currently has list $L$ and she wants to send her updates to Bob, she computes the diff between $L_{t-1}$ and $L$ and sends that diff to Bob.

• If both Alice and Bob concurrently made changes to their list, then you need to merge their diffs to form a new list.

• The result, after sychronization is $L_t$, which is known to both parties. Now go back to the beginning.

Now you have some design decisions that you can fill in various ways:

• How should Alice compute the diff between $L_{t-1}$ and her list $L$? One way is for her to keep track of a log of the changes she has made to the list since $L_{t-1}$ and use that as the diff (or possibly to compact that diff, e.g., if she inserts an item and then deletes it, no need to include that in the log of changes). Another way is for her to compute the diff between $L_{t-1}$ and $L$ from scratch, without keeping any logs.

• How should the diff be represented compactly, to minimize network bandwidth and make it as easy as possible for Bob to apply the diff?

• How should we merge Alice's diff and Bob's diff? There are many standard algorithms here; e.g., see source code revision control systems.

I hope that this was not already obvious. Your question did not make it entirely clear how much you already know about the general approach and what specifically you were looking for in an answer.