Re: efficient compare

Andersen schreef:

> Jan Hidders wrote:
> > Andersen wrote:
> >> Rephrasing it in math terminology:
> >> If I have two sets A, and B, containing tuples, and I want to find
> >> complement(A intersect B), how do I do that efficiently?
> >
> > Just as a small side note: since the worst-case communication
> > complexity of comparing two strings is O(n) where n is the length of
> > the strings you won't be able to do better than that in the worst case.
>
> Of course, but that is a worst case analysis. Roughly speaking (not
> exactly the same problem), I want to compare two strings and make one
> into the other (similar to RSYNC), but having to transfer as little as
> possible over the network.

That problem has clearly the same worst-complexity, and you already know an algorithm with that worst-case complexity (David Cressey's for example). If you want something that behaves better on average you first need to specify more precisely what "on average" means. It also depends a lot on what you can and cannot do on each client. Can we keep timestamps per key-value pair? Can we keep timestamps for each peer for the last moment of synchronization?

• Jan Hidders