Algorithm for syncing the order of entries

Question

This is client/server application system.

Client-part application can go off-line mode and sometimes syncs with server. (like GMail offline)

More than one client can connect to server, so each client can add, edit and remove its entries and synchronize these changes like SVN (the collision can be happend, but it's not a problem.)

The algorithm for adding, editing and removing entries is trivial. Server can make an unique ID for each new entries and clients use these ID for updating and removing.

The new requirement is the ordering of entries.

There are two client applicatin - x,y. And they stored entries - A, B, C and D. These entries array as D-C-B-A, so the order property of A is 4, B is 3, C is 2 and D is 1.

• x : D-C-B-A : A(4), B(3), C(2), D(1)
• y : D-C-B-A : A(4), B(3), C(2), D(1)

Client y create new entry E between D and C

• x : D-C-B-A : A(4), B(3), C(2), D(1)
• y : D-E-C-B-A : A(5), B(4), C(3), D(1), E(2)

After both client sync with server.

• x : D-E-C-B-A : A(5), B(4), C(3), D(1), E(2)
• y : D-E-C-B-A : A(5), B(4), C(3), D(1), E(2)

How can I synchronize these order information?

---

* Additional test *

Cient x remove D and C, but client y create new entry E between D and C.

• x : B-A : A(2), B(1)
• y : D-E-C-B-A : A(5), B(4), C(3), D(1), E(2)

After sync.

• x : C-B-A : A(5), B(4), C(3), D(1), E(2)
• y : C-B-A : A(5), B(4), C(3), D(1), E(2)

---

Answer 1

You might want to take a look at how FeedSync handles this problem (and several others) involved in synchronization.

Answer 2

The only difficult part is when an entry has been deleted, right? How about you keep the deleted entries on the server but tag them as deleted. Once all client have synchronized with the server so none of them know about the entry anymore, you can delete it permanently from the server too.

Answer 3

I believe that you should stick to the SVN protocol. You should not allow submitting without synchronizing (updating) to see if some changes occurred.

If you don't do that you will have big problems with the coherence (consistency) of stored data. For example you stored D - C - B - A and clients x and y are synchronized.

• client x removes C and A -> D - B
• client z synchronize, he obtains D - B and he adds F between D and B -> D - F - B
• meanwhile client y adds E between C and B -> D - C - E - B - A

Now if all clients will sync you cannot tell where F will be put in data sequence : D - F - E - B or D - E - F - B.