Subject: [VCARDDAV] Collision probabilities

From: "Darryl Champagne" <[email-masked]>
Date: Tue, 8 Jul 2008 13:02:19 -0400

Hi,
Per an earlier message (threat?), here is a standalone message on collision
probabilities.

There seems to be an ongoing concern to try and get rid of any possible
collisions (as in, get the probability down to the odds of creating a
duplicate GUID/UID).  My concern is for things to not be over-engineered, or
overly restricted without a good reason, and that we are already way down
the slope of diminishing returns.

First, let me refer people to the discussion of terminology in the email:
http://www.ietf.org/mail-archive/web/vcarddav/current/msg00437.html, at the
point beginning with "First, some background."

Specifically, I defined "Sync Anchors", "Slow Sync", "Object Level Duplicate
Detection", "Field Level Duplicate Detection", and discussed "Sync
Meta-Information" - meaning the information about the data being synced,
which is generally specific to a particular pair of devices being synced.
These definitions are not SyncML specific, they are general concepts that
apply to ActiveSync and other protocols as well (sometimes with different
names).

Now, every implementation, user set, and so on will have somewhat different
characteristics, but I can at least present some raw statistics.

Without being able to provide further details, on a particular SyncML server
with real users, over a particular logging cycle, here are some specific
numbers (rounded):

Regular/Fast Sync: 2,840,000
Slow Sync             36,700
Client-to-Server     184,000
Client Backup          2,400 (wipe all data from the server first)
Server-to-Client      68,600
Client Restore         2,000 (wipe all data from the client first)

Again, note that all statistics like this will vary greatly depending upon
the user population.  For example, in a corporate environment, you might
find a great deal more of Server-to-Client and Client Restore syncs, because
you may a population of devices that are not actually user-specific, and are
not allowed to propagate changes back to the server (you just reload them
periodically).

If one looks at the ratio of Slow Syncs to regular (fast) syncs, I get a
result that 1.3% of the syncs that occur without any of the Sync
Meta-Information available.  Now, at least some of these slow syncs are from
users who test something out, but do not keep using the product - e.g. they
perform an initial slow sync, perhaps a dozen fast syncs, and then stop
using it.  That is why I rounded it to a 1% chance of slow sync.  Different
user sets will have different behaviors, length of time of use, number of
syncs per day and so on, so I would expect the numbers from different
servers to vary - perhaps from 5% (doing a daily backup) down to .1%
(regular short interval syncs).

An important item to note is that Sync Meta-Information is specific to
particular pairs of devices.  Thus when we get into Triangle and up
situations, we are also talking about doubling and up the Meta-information
that has to be stored.  Unfortunately, in the real world, in addition to
Triangles causing problems directly with loops, they also cause data storage
problems.  Some implementations cannot keep change logs from multiple sync
anchors - when they sync with one server, they lose the Meta-information
specific to the other server, and will have to slow sync the next time.
This means that when we start talking about triangles and up, slow syncs are
more common, not less.

At this point, no solution that I know of can protect against all
collisions.  It is always possible for 2 independent devices to add, modify,
or delete data that happens to get the same PID (in the case of an Add).
The odds may vary, even all the way down to the chance of duplicate GUIDs,
but it is still possible.

So, given that we are going to make simultaneous changes to multiple
devices, some key questions are:

- What are the raw collision potentials of deletes and modifies?

If deletes collide, it is a non-issue - both sides deleted the same thing,
so we want that value gone.  If a non-colliding delete occurs - just on one
side, and it happens to be the 1% slow sync, then the delete may be lost,
and the data kept.

For Modifies - for the 99% of cases involving a fast sync, we hopefully know
which side has the correct data, and which side is new (which we do if only
one side changed the overall object - the only collision issue is when both
have touched the object - not necessarily touching the same field).  If we
don't have that info, we fall down into the 1% case below.

For Modifies - for the 1% of cases involving a slow sync, any modify has the
problem of detecting which side actually has the correct data.  Things like
the REV are useful, but not authoritative.  If both sides changed the vCard,
but only the first to change it modified a particular field, we have no way
of knowing this.  Essentially, if both vCards were changed, then we have a
collision - we know we have it, but we don't know which side has the correct
data for individual fields.  Because we are comparing the chances of
touching the vCard as a whole versus individual fields, I don't have the
information available to give a realistic number, but let's go with 1%.

- What are the raw undetected collision potential of Adds?

If I look at the LASTPID solution, it would appear that 2 devices both
adding a property to the same, already synced record will always collide on
the PID value.  If the next sync is one of the 1% of slow syncs, the
Meta-Information about what the LASTPID was at the time of the previous sync
will not be available, and it will be an undetected collision.

If I look at the order of magnitude random number generation scheme I
presented, then there is roughly a 1-2% chance of a PID collision (actually,
a 1 in 90 chance at first, increasing as high as 9 in 90, followed by a 1 in
900 chance, and so on).  Assuming you only get 1 or 2 possible collisions
(meaning we are not calculating the odds for adding 10, or a 100 new
properties to each between syncs), the odds stay closer to the 1-2% range
than the 10% range.  When duplicate PIDs happen to be created, we then need
to understand that in the 99% of regular syncs, they will be detected.  For
the 1% that are slow syncs, they will not, leading to an overall chance of
an undetected collision of roughly 0.02% (or call it .1% if you went with
10% above - none of these are going to be exact).

If PIDs were GUIDs, then you have roughly 1% of the chance of a GUID
collision (just call it very, very, small), but it is my opinion that this
is extreme overkill, and produces a very low signal to noise ratio. 

- What does a collision mean?

First, I am only looking at realistic scenarios.  One can create test
scripts that make hundreds of changes and all sorts of collisions, but I am
going to stick with real users.

So, if we have a real user, and there has been a change made to a field on
one device, and a change made to the exact same type of field on another
device, AND this happens to occur at the right time position in a sync
sequence, what does this mean?

My view is that the most typical reason for this to occur is the user
attempting to make the same change in multiple places.  For example, when
talking about totally new vCards, I receive a call on my Mobile Phone, and
save the number, probably with just a short name or identifier.  I then go
to my PC or PDA and create a real contact book entry for that person -
usually including additional information, like when they called me, and why.
Later, all the syncs catch up between devices, and Object Level Duplicate
Detection is critical.

For the case of just adding a single item to an existing vCard, I postulate
that this is pretty much the same case - I receive a call from a friend,
save his number, and then go update another copy of the data.  When I go to
sync, doing Field Level Duplicate Detection would seem to be the most
important issue, including resolving any formatting differences.  It seems
quite unlikely to me that I will add a new home telephone number to one
device, and also have reason to add a second, different new home telephone
number to another device (and not add the first), and expect to keep both.

Thus in my view, I postulate that a significant number of these possible
collisions are in fact not real collisions, and thus all the probabilities
need to be decreased accordingly.

- Which case is the most important?

When I look at these options, my view is:

Collisions on Deletes are not a big deal.  The worst case, if it is a slow
sync and only one side did a delete is that the item might not be deleted.

Collisions on Adds are not especially significant.  Most are not real, or
can be detected in the course of a regular sync anyway.  Cutting down the
odds via a random number, or any similar process seems to be more than
sufficient.  Using LASTPID or just creating new PIDs in sequence seems to
make them worse, but again, they are not typically going to be an actual
issue.

Collisions on Modifies are a real problem.  When a slow sync occurs, we can
play the odds, but do not have the information available to make an
authoritative decision.  It also seems like this would require REV
information per property to be able to actually solve, which seems like
un-realistic to implement overkill.  Basically, I do not have a safe
solution for this.  In some environments, like the non-user specific devices
in a corporate environment (e.g. the factory worker grabbing a device at the
start of their shift), data policies can dictate what happens.  Otherwise,
it may just have to be up to the particular implementation to allow the user
to select a policy - which is the way it generally works today - I give a
priority order to the data on my devices, for which one overwrites which
other ones.

Finally, in the real world, policies like today, to give a priority order
for where changes win (a conflict resolution policy), generally seem to be
sufficient.  What is missing is identifying which item was deleted or
modified, so that a field level replace can be done, and/or the association
with data not stored in the vCard is not lost (which small PIDs do just
fine).

Note that I also think it would be ridiculous to include text like the above
discussion in the RFC - way too much information.

Thanks,
dgc
--
Darryl G. Champagne
Technology Evangelist
Funambol
AIM/Y!/Skype: dgc03052
ph: +1 (603) 424-0323     Mob: +1 (603) 440-3621 (+ SMS)
[email-masked]          http://www.funambol.com 

_______________________________________________
VCARDDAV mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/vcarddav

---

From: "Darryl Champagne" <[email-masked]>
Date: Tue, 8 Jul 2008 17:56:59 -0400

Hi again,
Along with the collision probabilities discussed in the previous email, I
want to make sure people understand there are a lot of additional cases to
deal with (yet the previous email was already way too long), and in fact, a
number of them are more important than what was previously discussed.  My
real point was just to not get hung up worrying about a rare case like
collisions on Adds.

For example, we should try to ensure that PIDs do not get reused, if a
delete and an Add both occur.  It is pretty straightforward for a particular
implementation to just deal with this on its own, but the LASTPID idea could
formalize it.  Personally, I am fine with just a "SHOULD NOT reuse" in the
text, but it could be addressed in more formal ways.

I also want to be clear that I don't especially care either way regarding
the alternative proposal I made.  My preference is to not specify any
algorithm for choosing new PIDs - I don't think it matters very much.  If
you just want incrementing numbers in your particular implementation, that's
fine.  Just keep it very clear that they are not globally unique, their
purpose is to identify which particular instance was deleted or modified,
there will not be a lot of PIDs for each property, and collisions and
duplications of Adds must be dealt with somehow (especially so loops can
never start replicating things).  That's it - any attempt at explaining why
is going to be way too long.

dgc

> -----Original Message-----
> From: [email-masked] [mailto:[email-masked]] On
> Behalf Of Darryl Champagne
> Sent: Tuesday, July 08, 2008 1:02 PM
> To: [email-masked]
> Subject: [VCARDDAV] Collision probabilities
>