Conflict resolution for two-way sync

Question

How do you manage two-way synchronization between a 'main' database server and many 'secondary' servers, in particular conflict resolution, assuming a connection is not always available?

For example, I have a mobile app that uses CoreData as the 'database' on the iOS and I'd like to allow users to edit the contents without Internet connection. In the same time, this information is available on a website the devices will connect to. What do I do if/when the data on the two DB servers is in conflict?
(I refer to CoreData as a DB server, though I am aware it is something slightly different.)

Are there any general strategies for dealing with this sort of issue? These are the options I can think of:
1. Always use the client-side data as higher-priority
2. Same for server-side
3. Try to resolve conflicts by marking each field's edit timestamp and taking the latest edit

Though I'm certain the 3rd option will open room for some devastating data corruption.

I'm aware that the CAP theorem concerns this, but I only want eventual consistency, so it doesn't rule it out completely, right?

Related question: Best practice patterns for two-way data synchronization. The second answer to this question says it probably can't be done.

Answer 1

The usual solution for knowing "which change is correct" is a vector clock. You essentially keep track of counters for each repository that holds the data, and reject changes if a particular client's view of everyone else's state differs from that of the peer it is connecting to.

The big question that you have to answer is how you'll resolve rejected saves. This generally means some sort of merge operation.

Note that vector clocks do not use real-time timestamps. The problems involved in synchronizing real-time clocks is at least as difficult as synchronizing data.

Answer 2

This is the Byzantine Generals problem, which is unsolvable. You can never guaranteed synchronize the two servers if you cannot guarantee that at some time in the future, you will have sufficient reliable bandwidth to perform the synchronization all in one go.

Answer 3

I guess there is no standard way to do it, each system uses their own policies for the conflict resolution.

I made some simulations using two devices, computer and phone, and Google Spreadsheet to check how Google Docs handles conflicts automatically. Here some cases:

Case 1

1. Computer and phone are offline
2. Computer edit cell with value 'computer' and after phone edit cell with value 'phone'
3. Computer become online
4. Phone become online and both computer and phone displays 'phone'.

Case 2

1. Computer and phone are offline
2. Computer edit cell with value 'computer' and after phone edit cell with value 'phone'
3. Phone become online
4. Computer become online and both computer and phone displays 'computer'.

So at least Google Docs server use the last data it received as higher priority independently of when it was created (timestamp of the client). I also tested if they make sync in the background, and apparently they do not, so the result of the conflict resolution is transparent for the user.

GIT in other hand, does not handle conflicts automatically, but instead delegates to the last user that was trying to alter the repository how the merge should be done.

I would go for the Google Docs approach if it's okay only sync on the foreground, with the user visualising the data. Otherwise a user may be surprised that while his phone connected automatically to a WiFi a non sync change to a meeting that he after re-edited on his PC went live.

I would go for the client timestamp approach, overriding the conflicts with the last edited, if you need background sync, can trust the client timestamp and the cost of an undesirable merge is smaller than the cost of requesting the user to choose which version he wants to keep.

I would go for the GIT approach otherwise, by showing a popup in the next client in foreground asking the user to choose which version to keep or giving a chance to revert the merge.