Tombstone: a permanent marker that the ID once existed but has since been deleted.

Index: a set of items being managed with some unique ID

Difference: the set difference of items in one index and another

Instead of a tombstone a second "status" index is kept.

IDs are downloaded from remotes and copied to the status and local indices.

Deletions are checked against status to see if remote has modified the record since the delete; since the download would copy to status and local then anything in status but not local has been deleted.

Essentially tombstones are traded for a double-index.

But the double index will eventually forget about deleted content.

Algorithm

Synchronization

• For all items in A but not C; copy these items to B and C.
• For all items in C but not A; remove these itmes from B and C.

Full synchronization

• Synchronize(remote, local, status) -- download
• Synchronize(remote, local, status) -- upload