Synchronisation algorithms

Question

Are there any good references for synchronisation algorithms?

I'm interested in algorithms that synchronize the following kinds of data between multiple users:

• Calendars
• Documents
• Lists and outlines

I'm not just looking for synchronization of contents of directories a la rsync; I am interested in merging the data within individual files.

Answer 1

SyncML is a standard for data synchronization of things normally associated with someone's personal organizer. Nokia and Motorola were both using it heavily a few years ago, but I don't know its current state.

iCalendar is a calendar synchronization format specification, and CalDAV is an implementation of iCalendar atop the WebDAV protocol. Google searches for iCal or iCalendar will likely turn up the iCal application supplied by Apple as part of Mac OS X. Keep looking down the list of results until you see something which looks like a protocol.

Answer 2

There's a high-level and very broad overview of all synchronisation algorithms in Optimistic Replication (by Yasushi Saito and Marc Shapiro, PDF format).

Answer 3

I would have thought that looking at any of the open-source source code control applications would give you the right idea - merging changes between files is exactly what they do...

Answer 4

I believe Delta Compression is what you are looking for.