Subject: [VCARDDAV] Syncing and PIDs and UIDs (Oh my!)

From: Pete Resnick <[email-masked]>
Date: Mon, 7 Jul 2008 11:16:52 -0500

Try though I might to not get any work done in this group, I think I 
will try to break out of this pattern.

I've been going through the PID problem, and chatted with Simon, and 
I think I have come to a conclusion: PIDs must be monotonically 
increasing and unique throughout the vCard. That is:

      FN;PID=1:Jane Doe
      EMAIL;PID=1:[email-masked]

...wouldn't be acceptable. Instead, you'd need:

      FN;PID=1:Jane Doe
      EMAIL;PID=2:[email-masked]

Let me explain. If folks generally agree, I'll get to work on 
rewriting section 8.

First off, let me say that I've always felt that the vCard format 
should provide the tools so implementations that want to synchronize 
can do so. It does not mean that you're not going to have to write a 
bunch of code. It does not mean that there will not be duplicate or 
conflicting data that you have to deal with. It simply means that two 
devices that are playing by the same set of rules will have an easy 
time synchronizing and will not end up with data that makes the user 
crazy.

So, let's say that A and B are trying to sync what appear to be two 
identical vCards, and that they are the only two syncing devices (no 
triangles). The first time they sync, the two vCards might even have 
different UIDs which will be brought into sync. For this initial 
sync, neither PIDs nor UIDs buy you anything; we're having to figure 
out that these two vCards are actually one. However, once that's 
done, having a common UID for the two instances of the vCard and 
having identical PIDs is a big win. The next time we sync, it's easy 
to see what's changed, and I don't end up with duplicate properties, 
etc. (Note that we're only talking about two devices which actually 
support UIDs and PIDs. Devices that don't will have to do the 
"initial" syncing operation each time. Their loss.) However, we still 
do have the potential for a problem: If device A adds a new phone 
number, say:

            TEL;PID=10;TYPE=home:tel:+33-01-23-45-67

And unfortunately, device B adds a new phone number too:

            TEL;PID=10;TYPE=work:tel:+33-02-34-56-78

Let's say the REV on B's vCard is later than A's. Now, we go to sync. 
If we assume that those two properties are to be combined, we're 
going to do the wrong thing and end up throwing away A's new home 
phone number. What we want to have happen is for A to say, "B added a 
new phone number that it's calling PID 10" and for B to say the same 
of A and end up with both items. To accomplish this, A and B are both 
going to have to know which PIDs they've already synced and which are 
new. In order for that to work, PIDs are going to have to be 
increasing (I can't create PID 3 after I've created PID 4) and PIDs 
are going to have to be unique *throughout* the vCard (because 
otherwise I'm going to have to keep track of the last TEL PID, the 
last EMAIL PID, etc.).

This likely also means that, in addition to REV, we're going to need 
a LASTPID property.

So, before I go on to talk about the "triangle" problem, are people 
generally on board with the ideas I've talked about here?

pr
-- 
Pete Resnick <http://www.qualcomm.com/~presnick/>
Qualcomm Incorporated - Direct phone: (858)651-4478, Fax: (858)651-1102
_______________________________________________
VCARDDAV mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/vcarddav

---

From: Cyrus Daboo <[email-masked]>
Date: Mon, 07 Jul 2008 13:01:17 -0400

Hi Pete,

--On July 7, 2008 11:16:52 AM -0500 Pete Resnick <[email-masked]> 
wrote:

> This likely also means that, in addition to REV, we're going to need a
> LASTPID property.
>

Your example used FN;PID=1 etc. I thought we had decided that PIDs aren't 
needed on properties that occur only once. Are you proposing that we do 
need a PID on every property?

Also, I am assuming that once a PID has been assigned to a property it must 
never be changed?

One question arises - what happens if PID parameters are lost in 
transit/conversion. Chances are a PID-aware client that gets a vCard with 
stripped out PIDs will restart its PIDs from 1 again.

So how about we take a leaf out of the IMAP world, and as well as having 
PID and LASTPID, we also have PIDVALIDITY (similar to IMAP's UIDVALIDITY). 
PIDVALIDITY would be a unique token added to a vCard when a PID aware 
client first starts using PIDs. So, if another non-PID aware client were to 
strip the PIDs and the LASTPID property, then another PID-aware client 
would start PIDs at 1 again, but with a different PIDVALIDITY. Now it is 
possible to tell the difference between two vCards that are the same, but 
have different PID assignments due to one of them having been stripped and 
re-created. The difference in PIDVALIDITY being the indicator. Having 
PIDVALIDITY be a parameter on LASTPID would make sense.

This is very similar to IMAP where the tuple (UIDVALIDITY, UID) is the key 
for uniquely identifying a message in a mailbox. UIDVALIDITY changes when 
there has been a whole sale change in the mailbox (e.g. deleted and 
re-created).

So this does help in detecting the case where a non-PID aware intermediary 
has whacked the PID/LASTPID - it does not help in figuring out how to 
resolve the conflict. In this case a full field-by-field comparison would 
have to be done to figure things out with a big warning to the user, I 
guess.

-- 
Cyrus Daboo

---

From: Pete Resnick <[email-masked]>
Date: Mon, 7 Jul 2008 12:36:10 -0500

On 7/7/08 at 1:01 PM -0400, Cyrus Daboo wrote:

>Your example used FN;PID=1 etc. I thought we had decided that PIDs 
>aren't needed on properties that occur only once. Are you proposing 
>that we do need a PID on every property?

No, PID would only be required for properties that repeat. Though 
there's no harm in adding them to single occurrence properties.

>Also, I am assuming that once a PID has been assigned to a property 
>it must never be changed?

Well, more on this when we get to 3-way, but generally, correct. 
There's no harm in syncing PIDs, but it essentially becomes a "delete 
old, create new" operation.

>transit/conversion. Chances are a PID-aware client that gets a vCard 
>with stripped out PIDs will restart its PIDs from 1 again.

If I sync with another device that doesn't give me PIDs, then it 
essentially becomes a "new" sync again (i.e., field by field 
comparison). I don't have to renumber my PIDs if the other side 
doesn't give me any.

>So how about we take a leaf out of the IMAP world, and as well as 
>having PID and LASTPID, we also have PIDVALIDITY (similar to IMAP's 
>UIDVALIDITY).

I'm not convinced this is necessary or desirable. I don't think we 
want PID renumbering. But more on this when we get to multi-device 
sync (the "triangle" problem).

pr

---

From: "Darryl Champagne" <[email-masked]>
Date: Mon, 7 Jul 2008 14:09:28 -0400

Some notes on this, before a longer reply on the original...

> -----Original Message-----
> From: [email-masked] [mailto:[email-masked]] On
> Behalf Of Pete Resnick
> Sent: Monday, July 07, 2008 1:36 PM
> To: Cyrus Daboo
> Cc: [email-masked]
> Subject: Re: [VCARDDAV] Syncing and PIDs and UIDs (Oh my!)
> 

Except delete old, create new is a problem with PIDs and sync, because the
expectation (from a bunch of prior emails) is that a PID can be used to
correlate with other data related to the property, that doesn't get synced -
e.g. speeddial position, or private data like user interface position.
Delete old, create new means that the data is no longer in the same user
interface position.  Not nice if it's the same data (or logically the same
data, even if not the same value).

The PIDs sent to a particular device should be preserved if at all possible.

---

From: Pete Resnick <[email-masked]>
Date: Mon, 7 Jul 2008 14:21:01 -0500

On 7/7/08 at 2:09 PM -0400, Darryl Champagne wrote:

>>>Also, I am assuming that once a PID has been assigned to a 
>>>property it must never be changed?
>>
>>There's no harm in syncing PIDs, but it essentially becomes a 
>>"delete old, create new" operation.
>
>Except delete old, create new is a problem with PIDs and sync, 
>because the expectation (from a bunch of prior emails) is that a PID 
>can be used to correlate with other data related to the property, 
>that doesn't get synced - e.g. speeddial position, or private data 
>like user interface position. Delete old, create new means that the 
>data is no longer in the same user interface position.  Not nice if 
>it's the same data (or logically the same data, even if not the same 
>value).
>

Absolutely agree. But the key phrase is "if at all possible". There 
are going to be times (especially when we get to the triangle 
problem) when PIDs are going to have to change. But they should not 
be changed haphazardly.

pr
Qualcomm Incorporated

---

From: "Darryl Champagne" <[email-masked]>
Date: Mon, 7 Jul 2008 17:51:07 -0400

Hmmm, I see that as one way of addressing things, and it helps for one case.
Not sure it matters much, though.  I guess no major harm.

> Sent: Monday, July 07, 2008 12:17 PM
> To: [email-masked]
> Subject: [VCARDDAV] Syncing and PIDs and UIDs (Oh my!)
> 

Yes, definitely.  Expecting there to never be collisions or duplications is
completely unrealistic.

>             TEL;PID=10;TYPE=work:tel:+33-02-34-56-78

A minor nit, this example doesn't match prior ones - which talked about
identical properties _and_ types.  Since you have two different types, it is
already clear you have two different values, just like today, where you
don't have PIDs.  I don't think we want to tell implementers to use less
information than they already have available today.  To match prior
examples, we should treat this as 2 new home numbers (which is also less
likely to actually occur).

> This likely also means that, in addition to REV, we're going to need

I have a bit of concern about the consistency issue, and heading down a
slippery slope of adding global data (as opposed to per value data), that
doesn't actually solve the problem (just one piece of it).  By having a
stored LASTPID per vCard (which isn't the current value), we can identify
all PIDs on this side that are newer than the last sync, but we don't know
anything about which other PIDs may have been changed or deleted, or what
other fields are new, modified, or deleted.  It still may be worth doing,
but people need to realize it is nowhere near sufficient to address doing
sync correctly (and I sure hope we don't head towards a REV per field).

Take the above example, except make both phone numbers a new type=home
number.  Also have existing work numbers which change.

At the time of the last Sync:
Device A & B:
      FN:Jane Doe
      REV:2008-01-01 <-- Note Time 1
      EMAIL;PID=2:[email-masked]
      TEL;PID=7;TYPE=work:tel:+33-03-33-33-33
      TEL;PID=8;TYPE=work:tel:+33-04-44-44-44
      TEL;PID=9;TYPE=home:tel:+33-05-55-55-55
      LASTPID:9

At the time of the next sync:
Device A:
      FN:Jane Doe
      REV:2008-01-02 <-- Note Time 2
      EMAIL;PID=2:[email-masked]
      TEL;PID=7;TYPE=work:tel:+33-06-66-66-66 <-- Note change
      TEL;PID=8;TYPE=work:tel:+33-04-44-44-44
      TEL;PID=9;TYPE=home:tel:+33-05-55-55-55
      LASTPID:10
      TEL;PID=10;TYPE=home:tel:+33-01-23-45-67 <-- New Home #

Device B:
      FN:Jane Doe
      REV:2008-01-03 <-- Note Time 3
      EMAIL;PID=2:[email-masked]
      TEL;PID=7;TYPE=work:tel:+33-03-33-33-33
      TEL;PID=8;TYPE=work:tel:+33-07-77-77-77 <-- Note other change
      TEL;PID=9;TYPE=home:tel:+33-05-55-55-55
      LASTPID:10
      TEL;PID=10;TYPE=home:tel:+33-02-34-56-78 <-- Second New Home #

Desired Record:
      FN:Jane Doe
      REV:2008-01-04 <-- Note Time 4
      EMAIL;PID=2:[email-masked]
      TEL;PID=7;TYPE=work:tel:+33-06-66-66-66 <-- Note change from A
      TEL;PID=8;TYPE=work:tel:+33-07-77-77-77 <-- Note other change from B
      TEL;PID=9;TYPE=home:tel:+33-05-55-55-55
      LASTPID:11
      TEL;PID=10;TYPE=home:tel:+33-01-23-45-67 <-- New Home # from A
      TEL;PID=11;TYPE=home:tel:+33-02-34-56-78 <-- Second New Home # from B

Here is the basic issue.

LASTPID let you identify that the two PID=10 values were different, and to
correctly deal with them.

However, if that is all you have, then didn't you just lose the PID=7
change?  Device B was a newer REV, so what can you base your change info on?

So how are you going to know that PID=7 changed on Device A (Assuming that B
is doing the merge, after being sent the record by A, before it sends the
merged record back to A)?

Unless you kept the record from REV:2008-01-01 available, or some similar
additional data, how can you make the "correct" decision to use the changed
PID=7 telephone number?

Now, if I have the REV:2008-01-01 record available, then LASTPID didn't do
anything for me - I already know that I (device B) have a new PID=10, and
that device A just sent me a new PID=10 that is different.  The issue isn't
with collisions on new values - I already have that information, the issue
is identifying which existing value changed.

Now, there are other options - for one of many, I (device B) could instead
have a flag per line of the vCard, to indicate which fields have been
modified.  That would correctly deal with all lines modified by A which were
not modified by B, which in this case would pick up the PID=7 change.
However, that would not directly pick up that both PID=10's were new, since
I can't indicate in the vCard which specific lines have been modified.  Note
however that SyncML does support this, as I can send a field level update,
and send only those fields that have changed.  If I am not using SyncML
Field Level Updates, then I could use LASTPID to be able to pick up that
both PID=10's were new, so only it that case would it be helpful.  Also,
before people jump over storing lots of data, remember that sync today
frequently deals with very asymmetric environments - big servers, and small
devices.  We have to work with both, not require everyone to be simple.

This same issue applies to all other fields, that don't have PIDs - in order
to correctly sync the objects, you must know other information, which at
least some of the time will duplicate the LASTPID info.  The problem that
drove the request for PIDs isn't picking up what is new, it is identifying
_which_ old thing was changed or deleted.

> generally on board with the ideas I've talked about here?

We also have some terminology issues, in that we are using the same term to
mean different things - "initial" sync.

First, some background.  In order to successfully sync objects more than
once, you generally want to have some meta-information about those objects.
In several sync protocols (like ActiveSync and SyncML), this means that you
have protocol level identifiers for each object, as well as some indication
of when you last performed a sync between those pairs of objects ("Sync
Anchors").  The protocols have to support more than just vCard, live with
time differences and such, and thus do not rely upon internal identifiers or
date/rev information for the general case.  Note that if you are not
allowing multiple asynchronous changes, then you don't need sync - simpler
protocols will work fine.

Note that protocol level identifiers are generally unique to the pair of
devices, at least when a sync begins.  This is to allow for what is
generally called duplicate detection - if I have essentially the same record
on both devices, someone has to be able to match them, and tell the other
side to use a different identifier, or keep a mapping table between values.
Even if the device creates a GUID for an identifier, when duplicates are
detected the other side has to either keep a mapping, or tell the first
device to use a different GUID.  For clarity against the text above, I will
call this "Object Level Duplicate Detection".  Note that this is a very
costly operation - you have to compare (some sub-set of) every record on one
side with every record on the other.

This Meta information is generally used - so even if there are no UIDs on
records, the mapping is still usually known.  This means that "Object Level
Duplicate Detection" is only done on records that are new to both sides at
the time of a particular sync.

If the Meta information is not available for some reason - such as this
being the very first sync ever, or it was lost for any number of scenarios
shown in previous emails, then SyncML (unfortunately) calls this a "Slow
Sync", or it can be called a Full Sync, or a Recovery Sync.  A reasonable
assumption is that Slow syncs occur at least 2 orders of magnitude less
frequently than syncs that do have meta-information (e.g. 1 in a 100 or less
- based on real-world data).  In this 1% or less case, or when there are
multiple new objects on both sides, UIDs are helpful to decide what records
to compare first, but otherwise they really are not needed to do pair-wise
sync (they help much more in triangle and up).

I want to stress the "typical" behavior - because even if one side does not
support UIDs, that does not usually result in the "initial" behavior
mentioned above.

Similarly, if an object has changed, then you need to decide what parts of
the object have changed.  It is this case where PIDs will enter.
Specifically only for the case of multiple new fields being added, we would
have "Field Level Duplicate Detection".  Most of the time, the value in PIDs
is identifying which existing field was changed.

----
Now, rather than continuing with the basics, let me jump ahead to an
alternative method.  It's neither ideal nor especially clean, but I expect
it is good enough.

This is just going to be based upon reasonable rule-of-thumbs, that won't
fail catastrophically.  It's also not something I was planning on
specifying, just vaguely how I was thinking of implementing it.

- PIDs should (not must) be unique for each specific property - E.g. Email,
or Tel.  Any duplicate PIDs being sent indicates an existing conflict, which
someone should resolve.

- When a vCard is created (or rather, all modifications until a Sync occurs,
if that can be identified), all PIDs are assigned sequentially.  This is not
required, it is just easier to read and debug.

- Implementations should have a general expectation as to how many values
for a particular property it can support.  If there is no limit, then go for
something like whichever is largest: 16, or double the actual number in use
(or just 9 or 16 - be real, how many people have dozens of phone numbers).

- When creating a new value for a PID based property, generate a random
number from a range at least an order of magnitude larger than the range
above.  For example, since bytes over the wire is based on text characters,
if there are 9 or less, then allocate a random number between 10 and 99 (or
1 and 99, or 0 based, whatever is desired).  If you are using 16, then
allocate from 17-255.  Then test to ensure that the value is not already in
use.  If it is, then just keep incrementing until you find an unused value
(which will never fail).

The basic behavior would be:

When you first create the object, you typically have single digit PIDs.

While you have a small number of values, e.g. 0-9, and you create new
values, you allocate a random value up to 99.  That is a pretty small chance
of a collision (and only at most a 10% chance of even colliding with an
existing, known value, which can be detected).  This means you will start
with things like PID=35, PID=77, etc. - nothing too long to transmit.

If you start getting a larger number of values, e.g. 10-99, you are now
allocating from values up to 999.  Now you are dealing with 3 digit PIDs.

For people who prefer powers of two - while you have <16, allocate an 8 bit
random number.  When you have 16 < x < 255, allocate 16 bits, or whatever.

-
Now, before people jump all over the 1-10% chance of collision, keep in mind
that we are talking about real people, with real data, and we are not
talking about hundreds of the same properties in a single vCard, with
hundreds of them changing between syncs (and if we were, then LASTPID would
also being going up quickly).  In a pair-wise sync, you have to know which
values are new already, so that is not a collision.  Even for triangle and
up situations, we are talking about just a few special case situations where
a chance of a collision is even possible.  I personally am focused more on
just making sure I know which existing value has changed, as that is the
typical problem case.

Additionally - what is reasonable to consider as the most typical scenario
where (e.g.) a new home number is entered on multiple devices from a single
user?  If you are actually talking about real people - this almost always
happens because the user is trying to add the same information multiple
places.  That means that the vast majority of these so-called collisions are
actually duplicates (possibly with formatting differences).  All of these
new PIDs need to have Field Level Duplicate Detection done on them.
Sometimes there are typos, but in the real world most of these are not
supposed to be 2 new entries.

Now, you could still use LASTPID, but the bulk of what you really are
gaining is not needing to check for a collision between your new random
value and the existing values - it's a rare user interface that allows more
than 5 email addresses or telephone numbers.

LASTPID is a good way of doing things, and at least it is relatively
deterministic for new values, but people have to be aware that it has to be
in addition to pretty much the same information anyway if your sync is going
to succeed.  So far, I don't see any real harm from it (other than
preventing implementations from being able to use PIDs directly as local
keys, or trying to be clever and add extra info to them), and specs are more
likely to implemented correctly with simple directions, so it may be worth
doing.

---

From: "Darryl Champagne" <[email-masked]>
Date: Mon, 7 Jul 2008 23:14:53 -0400

> Behalf Of Cyrus Daboo
> Sent: Monday, July 07, 2008 1:01 PM
> To: Pete Resnick; [email-masked]

> there has been a whole sale change in the mailbox (e.g. deleted and

A couple of things about this.  Do you want a data interchange format, or a
Sync protocol?  At the Sync Protocol level, you identify if both sides have
valid change logs, matching starting points (sync anchors), and if the Sync
IDs are still valid.  I'm not sure it really makes any sense to add this to
each data item as well.  

Additionally, sync has different requirements than IMAP.  I can't flush and
reload - if I used to have the same data on both sides, then no matter what
has happened to the data and IDs, I need to make a best effort at detecting
duplicates, and merging changes.  In IMAP, the actual records don't change
(just flags).  In sync they do.  You don't expect an IMAP server to match a
brand new message ID with an existing message that is close to it on a
device - that is just a new message with similar data.

Regarding PIDVALIDITY, like Peter said, if that device doesn't have valid
PIDs, it shouldn't send them.  Much more significant is that if it has a
whole new set of PIDs because of syncing with some other party, then the
concept of validity isn't meaningful - those PIDs are valid between the
device and the other party, but they aren't valid between the device and me.
Similarly, the whole LASTPID thing doesn't help detect conflicts unless you
know what the LASTPID value was at the previous sync between this particular
pair of devices.  If you just try to merge two vCards without a history
specific to the current pair of devices, you haven't done anything about
conflicts.

This, like any information that is only locally meaningful - e.g. between a
particular pair of devices, doesn't belong as part of the data - that is
sync metadata.
 
> have to be done to figure things out with a big warning to the user, I

I would be careful about this part - user interaction on a limited device is
very limited.  You might be able to stick something in a log on the server
that the user might see if they use the portal, but don't assume that a user
interaction is possible (or desirable).

---

From: Pete Resnick <[email-masked]>
Date: Tue, 8 Jul 2008 17:25:02 -0500

Darryl, I'm going to address the second part of your message in a 
second message, but I wanted to answer these before sending that. It 
might be worth waiting for my followup before you reply, but feel 
free either way.

On 7/7/08 at 5:51 PM -0400, Darryl Champagne wrote:

>>If device A adds a new phone number, say:
>>
>A minor nit, this example doesn't match prior ones - which talked 
>about identical properties _and_ types.  Since you have two 
>different types, it is already clear you have two different values, 
>just like today, where you don't have PIDs.  I don't think we want 
>to tell implementers to use less information than they already have 
>available today.

OK, was getting too cute in my example. I was trying to make the 
distinction between two new items and two changed items. If PID=10 
was already synced as it was in A and B *changed* the item to 
"TYPE=work:tel:+33-02-34-56-78", then the right thing for A to do is 
delete PID=10 and replace it with the one from B. If they're both 
new, then they should both be kept.

>By having a stored LASTPID per vCard (which isn't the current 
>value), we can identify all PIDs on this side that are newer than 
>the last sync, but we don't know anything about which other PIDs may 
>have been changed or deleted, or what other fields are new, 
>modified, or deleted.

I think I disagree. If I can tell, e.g., that PID=10 has already been 
synced (and I know that the chap I'm syncing with is following the 
rules, an admittedly big caveat), then I know that if the property 
with PID=10 is different on the remote end, it is a change of my item 
marked with PID=10.

>Take the above example, except make both phone numbers a new 
>type=home number.  Also have existing work numbers which change.
>

OK, so the last synced PID is 9.

>       TEL;PID=10;TYPE=home:tel:+33-01-23-45-67 <-- New Home #

No, LASTPID is wrong here. We haven't synced PID=10, so before the 
sync, LASTPID is still 9.

>       TEL;PID=10;TYPE=home:tel:+33-02-34-56-78 <-- Second New Home #

OK, but same as above. LASTPID:9.

>       TEL;PID=11;TYPE=home:tel:+33-02-34-56-78 <-- Second New Home # from B

Right, that's what I would expect.

>Here is the basic issue.
>
>LASTPID let you identify that the two PID=10 values were different, 
>and to correctly deal with them.

Correct.

>However, if that is all you have, then didn't you just lose the 
>PID=7 change?  Device B was a newer REV, so what can you base your 
>change info on?

No, I would expect B to get this right. Using only LASTPID and REV 
won't solve its problem, but at least I never expected it to solve 
these sorts of issues in the absence of other info. For a simple B 
(and it is the simple devices for which I think we need to have 
support in the spec),  B would keep track of which fields it changed 
(either per field or hanging on to the previous vCard), and when it 
sees that A changed PID=7 but it has not, it updates PID=7 (ignoring 
who has the later REV).

>Now, there are other options - for one of many, I (device B) could 
>instead have a flag per line of the vCard, to indicate which fields 
>have been modified.  That would correctly deal with all lines 
>modified by A which were not modified by B, which in this case would 
>pick up the PID=7 change.

True. Are you suggesting that we also have a per-property CHANGED 
parameter? We could do that, but my conception has always been that 
we want just enough information in the vCard for the simplest of 
devices to "do the right thing". In my view, having PID for 
multi-occurrence properties plus LASTPID is enough for a simple 
device to do the right thing (assuming it keeps track of what it 
itself changed). If the expectation is that for most simple devices, 
they are going to hand off their copy of the vCard to some other 
entity to sync/merge and then get back a new one, then perhaps a 
per-property CHANGED flag makes sense.

>However, that would not directly pick up that both PID=10's were 
>new, since I can't indicate in the vCard which specific lines have 
>been modified.

That's what LASTPID:9 gets you. You know that both 10s are new.

>If I am not using SyncML Field Level Updates, then I could use 
>LASTPID to be able to pick up that both PID=10's were new, so only 
>it that case would it be helpful.

LASTPID also tells you that both PID=7 and PID=8 need to be merged. 
It doesn't tell you which value wins. For that, you need to know 
whether or not your value changed.

>This same issue applies to all other fields, that don't have PIDs - 
>in order to correctly sync the objects, you must know other 
>information, which at least some of the time will duplicate the 
>LASTPID info.

I'm not sure what this implies. Do you mean we don't need LASTPID? Do 
you mean we don't need PID? Or do you simply mean that PID and 
LASTPID don't solve all of our problems? (If the last, I completely 
agree.)

>The problem that drove the request for PIDs isn't picking up what is 
>new, it is identifying _which_ old thing was changed or deleted.

Correct. And that it does.

More to follow....

pr

---

From: "Darryl Champagne" <[email-masked]>
Date: Tue, 8 Jul 2008 20:07:41 -0400

First a quick reply, since there is a major flaw here.

You have the LASTPID value not being updated until the next sync.  However,
if you look at how I described a Slow Sync, it is where you have lost all
meta information specific to this pair of devices, such as through a
software upgrade, device reset, or so on.  Clearly, LASTPID is going to be
specific to each pair of devices - since I synced at one point with one
device, and perhaps another point with another device.  If it isn't global
information, then the 2 different LASTPIDs, one for each device, are not
going to be available during a slow sync.

Unless you somehow want a LASTPID that also carries some device identifier
for who it is relevant for, and have one for every device that you ever sync
with?

> From: Pete Resnick [mailto:[email-masked]]
> Sent: Tuesday, July 08, 2008 6:25 PM
> To: Darryl Champagne
> Cc: [email-masked]

Yet this is way smarter than the simple devices I described.  A smart device
could keep track of which fields it has changed, but a simple device could
not - device B is smart in this description.

> parameter? 

NO! I thought my later sarcasm was clear about this, but anyway.

> We could do that, but my conception has always been that

---

From: "Darryl Champagne" <[email-masked]>
Date: Tue, 8 Jul 2008 23:22:43 -0400

Ok, the detailed response.
Note I sent separate terminology notes, because we are not using terms the
same way.

> with PID=10 is different on the remote end, it is a change of my item

OK, the examples are getting confused here (PID=10 synced already or not).
If we talk about PID=7 which definitely has been synced, the point was just
that LASTPID can't tell you if PID=7 changed at all, locally or remotely.
That has to be done through totally separate information, like comparing the
two vCards (and the information about the original isn't available in what I
called a simple device). 

> sync, LASTPID is still 9.

Here we start heading in different directions.  First of all, in terms of
the details of what I was describing, the sync begins with A sending its
changes to B (the entire new vCard, if A is a simple device).  B then can
decide how it wants to merge those changes in with it, and it can send any
updates back to A.  We don't have any globally visible storage that both
sides can see, or anything like that.

In order for LASTPID to still be 9, that either means that device A has to
keep a separate LASTPID for each server it syncs to, or else it hasn't done
a sync with anyone else.  That wasn't how I read your description of
LASTPID, but that is my fault.  In any case, LASTPID, or any PIDs are not
going to be stored in the native address book of a simple device.

> sees that A changed PID=7 but it has not, it updates PID=7 (ignoring

Again, I was discussing that unless you kept track of which fields were
changed, or had the original vCard, which is beyond the capabilities of a
simple device....

> True. Are you suggesting that we also have a per-property CHANGED

Again, just to be safe, No.

> per-property CHANGED flag makes sense.

And here we almost talk about the same devices - that last part was what I
was talking about.  Regarding per-property changed flags, I don't want it in
the vCard because I already have that ability in the Sync Protocol.  I can
send a Field Level Update that just contains the properties that have
changed (plus Begin, End, and N to make it a legal vCard).  I don't want to
send an entire new vCard, I just tell the other side my differences from
what it sent me.

> whether or not your value changed.

But in fact it isn't LASTPID that tells you 7 and 8 have changed, it is that
you can identify that those fields have changed all on your own by comparing
them.  A standalone LASTPID of 9 or 10 tells you nothing new about 7 or 8.
That's all I was talking about.

> LASTPID don't solve all of our problems? (If the last, I completely

The last part, we agree on.

However, my point was that if you have the original vCard as well as your
current data, then LASTPID is just repeating information you already have -
you don't need it.  Just by comparing old with new with what you got from
the other side, you can identify all about PID=10 being new (it wasn't in
the old vCard), as well as figuring out PID=7 and PID=8, which is something
you already have to do.

We actually still have a slight issue in how to describe that what used to
be PID=10 on B is now PID=11.  It isn't a direct issue in this pair-wise
sync, because if I as device B am making the change, I can just do it before
sending it - but if I then want to re-sync back with someone else (but now
as a client), we have problems (or need to have
TEL;PID=11;OLDPID=10;TYPE=home:tel:+33-02-34-56-78).

The big thing I see LASTPID actually doing for you is to make it easier to
avoid deleting a PID, and reusing that number - but it makes things worse
for the slow sync case.  You are using it as a Sync Anchor for part of the
data, yet for the sync to work you already have to have a valid sync anchor
for the entire vCard.  Sure, you can use it, but there isn't anything that
actually requires it.

Now as per later emails - the case of preventing the reuse of a PID after a
delete is actually one of the cases that I consider more significant.  It
may be worth doing LASTPID just for that, but this isn't an overwhelming
advantage.

> Correct. And that it does.

And I am sure that a detailed analysis of my alternate proposal will show
that it sucks - but is it good enough, and when you look at actual slow sync
numbers (in the collision probability email), you can see it actually ends
up better than LASTPID for the cases being discussed....

---

From: Pete Resnick <[email-masked]>
Date: Fri, 25 Jul 2008 13:29:37 -0500

Finally catching up....

On 7/8/08 at 8:07 PM -0400, Darryl Champagne wrote:

>[...]
>Unless you somehow want a LASTPID that also carries some device 
>identifier for who it is relevant for, and have one for every device 
>that you ever sync with?

That's what I was going to get to with my "triangle problem" 
thoughts, which I have not yet typed up. But let's talk about the 
rest first:

On 7/8/08 at 11:22 PM -0400, Darryl Champagne wrote:

>the point was just that LASTPID can't tell you if PID=7 changed at 
>all, locally or remotely. That has to be done through totally 
>separate information, like comparing the two vCards

Agreed.

>(and the information about the original isn't available in what I 
>called a simple device).

OK, this may be what a lot comes down to. As you say later:

>In any case, LASTPID, or any PIDs are not going to be stored in the 
>native address book of a simple device.

OK, so this is really the crux of it. I agree that some devices will 
not have PIDs (or LASTPID), but syncing with such a device 
effectively means always doing a slow sync (or something not much 
more impressive than that using what I consider weak 
meta-information). Along with that, such devices are always going to 
have the "delete the wrong phone number" or "duplicate data" 
problems. If you want to call anything that has PIDs a "mid-level" 
device, fine. In that case, I'm saying I don't care much about 
"simple" devices (where "care about" means "want to design lots of 
general infrastructure around"). What I want is enough support in 
vCard for a mid-level device to do the right thing.

Getting back to the discussion:

>In order for LASTPID to still be 9, that either means that device A 
>has to keep a separate LASTPID for each server it syncs to, or else 
>it hasn't done a sync with anyone else.  That wasn't how I read your 
>description of LASTPID, but that is my fault.

No, my fault. I was leaving the discussion of different LASTPIDs (and 
some possible other items) until later. I wanted to see if the whole 
idea got any traction first.

>>my conception has always been that we want just enough information 
>>in the vCard for the simplest of devices to "do the right thing". 
>>In my view, having PID for multi-occurrence properties plus LASTPID 
>>is enough for a simple device to do the right thing (assuming it 
>>keeps track of what it itself changed). If the expectation is that 
>>for most simple devices, they are going to hand off their copy of 
>>the vCard to some other entity to sync/merge and then get back a 
>>new one, then perhaps a per-property CHANGED flag makes sense.
>
>And here we almost talk about the same devices - that last part was 
>what I was talking about. Regarding per-property changed flags, I 
>don't want it in the vCard because I already have that ability in 
>the Sync Protocol. I can send a Field Level Update that just 
>contains the properties that have changed (plus Begin, End, and N to 
>make it a legal vCard). I don't want to send an entire new vCard, I 
>just tell the other side my differences from what it sent me.

Fair enough. What I'd like (and I think we're now talking about 
"mid-level" devices) is to have enough info in the vCard to do a 
reasonable job of syncing without a *lot* of out of band syncing 
information. I am not convinced (as you are) that low-end devices 
will always be throwing away PIDs and relying on sync engines; I 
think they'll evolve to take advantage of tools we provide them in 
vCard. But even if you're right, that doesn't mean that we shouldn't 
provide those tools for mid-level devices.

>But in fact it isn't LASTPID that tells you 7 and 8 have changed, it 
>is that you can identify that those fields have changed all on your 
>own by comparing them.  A standalone LASTPID of 9 or 10 tells you 
>nothing new about 7 or 8. That's all I was talking about.

We agree. You need LASTPID to know which fields are new and which 
ones are old, but you don't need LASTPID to figure out which ones 
changed; that you do by comparing vCards (or flags or...).

>However, my point was that if you have the original vCard as well as 
>your current data, then LASTPID is just repeating information you 
>already have - you don't need it.

Correct.

>We actually still have a slight issue in how to describe that what 
>used to be PID=10 on B is now PID=11. It isn't a direct issue in 
>this pair-wise sync, because if I as device B am making the change, 
>I can just do it before sending it - but if I then want to re-sync 
>back with someone else (but now as a client), we have problems (or 
>need to have TEL;PID=11;OLDPID=10;TYPE=home:tel:+33-02-34-56-78).

In the triangle sync, you'd have to keep track of this stuff. That's 
the big problem to solve.

>Now as per later emails - the case of preventing the reuse of a PID 
>after a delete is actually one of the cases that I consider more 
>significant. It may be worth doing LASTPID just for that, but this 
>isn't an overwhelming advantage.

If it's useful for sync in general, yes.

>And I am sure that a detailed analysis of my alternate proposal will 
>show that it sucks - but is it good enough, and when you look at 
>actual slow sync numbers (in the collision probability email), you 
>can see it actually ends up better than LASTPID for the cases being 
>discussed....

I have some comments on it, but it doesn't "suck". The big question 
for me is, what is the *easiest to implement* way to handle syncing 
such that a relatively lightweight client has the tools in the vCard 
to do it.

pr

---

From: Pete Resnick <[email-masked]>
Date: Fri, 25 Jul 2008 13:34:48 -0500

On 7/7/08 at 5:51 PM -0400, Darryl Champagne wrote:

>let me jump ahead to an alternative method. It's neither ideal nor 
>especially clean, but I expect it is good enough.
>[...]
>- Implementations should have a general expectation as to how many 
>values for a particular property it can support. If there is no 
>limit, then go for something like whichever is largest: 16, or 
>double the actual number in use (or just 9 or 16 - be real, how many 
>people have dozens of phone numbers).

OK, so here's my big question: Why? Does adding 2-bytes to every 
field really make a difference to a mid-level implementation? That'd 
give you 65536 PIDs, which should always be more than enough, and we 
wouldn't have complaints about collisions.

>Now, you could still use LASTPID, but the bulk of what you really 
>are gaining is not needing to check for a collision between your new 
>random value and the existing values - it's a rare user interface 
>that allows more than 5 email addresses or telephone numbers.
>
>deterministic for new values, but people have to be aware that it 
>has to be in addition to pretty much the same information anyway if 
>your sync is going to succeed. So far, I don't see any real harm 
>from it (other than preventing implementations from being able to 
>use PIDs directly as local keys, or trying to be clever and add 
>extra info to them), and specs are more likely to implemented 
>correctly with simple directions, so it may be worth doing.

So what is the advantage of your solution over LASTPID?

pr

---

From: "Darryl Champagne" <[email-masked]>
Date: Fri, 25 Jul 2008 15:47:53 -0400

> Sent: Friday, July 25, 2008 2:35 PM
> To: Darryl Champagne
> Cc: [email-masked]

Does it make a difference to the App - No.  However, I like to stick with
smaller while I can, because it is easier to read and debug PID=3, than
PID=17249, or even PID=74 if you meant 2 bytes ascii.  Again, my preference
is to not document any algorithm, I don't think it is needed.

> So what is the advantage of your solution over LASTPID?

For that, you need to read the thread on collision probabilities, which went
into a fair bit of detail on exactly that.  Unless you want it cut and
pasted here...

---

From: "Darryl Champagne" <[email-masked]>
Date: Fri, 25 Jul 2008 16:39:45 -0400

> Sent: Friday, July 25, 2008 2:30 PM
> To: Darryl Champagne
> Cc: [email-masked]

...
 
> vCard for a mid-level device to do the right thing.

OK, but it involves a lot more than just _only_ simple devices.  It applies
to Microsoft Outlook, Exchange, Lotus Notes, and so on.  Sync clients for
those address books all have to deal with not being able to store any of
that Meta-information in the native address book (at least in a reusable
form).  They all then have to deal with that 1%, or .1%, or whatever it
might be in the future, where that Meta information isn't available - please
refer to the collision thread.  ActiveSync works for Outlook, without any
vCard support at all - I don't see any migration occurring there, so the
problem is going to remain for a while (until Outlook 2007 is so obsolete it
doesn't need to be worried about).

I agree that we don't want a huge amount of infrastructure created just for
low end devices, but I also don't want to create infrastructure that only
helps a tiny bit for other devices when everything goes well, and really
hurts the low end ones a lot, as well as meaning that every little problem
with Outlook etc. ends up causing problems.  LASTPIDs make the best case a
minor amount simpler to define and implement, while making the worst case
noticeably worse.  That does not seem to be a good tradeoff to make. 

None of this is talking about designing lots of general infrastructure -
this is just saying that using LASTPIDs is very bad for a number of
important cases - much worse than just grabbing random numbers.  I'm the one
talking about having less defined, not more.

> ...

That's where I looked into probabilities.  LASTPID has the worst behavior of
all possible options when meta-information is lost - it almost guarantees an
undetected conflict.  I would prefer to just have a simple statement that
devices SHOULD not reuse PID values from properties that they delete
(actually meaning delete and reuse before the next sync).

> such that a relatively lightweight client has the tools in the vCard

Easiest way "to specify" is pretty much what is currently specified (meaning
the RFC doesn't say), perhaps with the one line from above about reuse.
Then the Sync protocols specify more when needed.  If you are doing a
mid-level device, then your implementation would be free to do whatever is
simplest for "that particular implementation to implement" - keep its own
internal LASTPID type of value just to satisfy that, and always use an
incrementing value (or just mark PIDs as deleted to avoid reuse - whatever
works for it).  If it loses meta-information, it can regenerate at least its
own values to avoid.  A more sophisticated implementation could do more, and
deal with syncing with other parties.  If you want guidance, like an
implementation MAY internally keep a LASTPID, that's fine, but I'd like to
the option to do something different to work better with low end devices &
other people's address book managers.

Also note that LASTPID causes more problems when a merge happens, because
now we have to worry about PID values being unique throughout the vCard,
rather than just unique within Email, tel, etc.  That makes it more likely
that we will have to renumber existing PID values whenever we merge vCards -
even if it just the single Email property was PID=1 in one card, and the
single Tel (without any email properties) was PID=1 in the other vCard.  I
don't know how to quantify that in any meaningful way, however.

---

From: Pete Resnick <[email-masked]>
Date: Sat, 26 Jul 2008 18:53:57 +0100

On 7/25/08 at 3:47 PM -0400, Darryl Champagne wrote:

>>field really make a difference to a mid-level implementation? 
>>That'd give you 65536 PIDs, which should always be more than 
>>enough, and we wouldn't have complaints about collisions.
>
>Does it make a difference to the App - No.  However, I like to stick 
>with smaller while I can, because it is easier to read and debug 
>PID=3, than PID=17249, or even PID=74 if you meant 2 bytes ascii.

OK, so "easier to read and debug" is one reason.

>For that, you need to read the thread on collision probabilities, 
>which went into a fair bit of detail on exactly that.

No, the 2 collision messages (not really a thread; nobody responded) 
talk about why collisions are not such a bad thing. They do not 
discuss the positives of an approach that has collisions. So far, 
I've got "easier to read and debug". What other reason is there for 
taking your approach?

pr

---

From: "Darryl Champagne" <[email-masked]>
Date: Sat, 26 Jul 2008 23:59:44 -0400

Shortened copy of summary at the bottom, for those not willing to read all
the way through:

LASTPIDs compare 100x worse for collisions in Adds
LASTPIDs compare roughly the same for Deletes
LASTPIDs compare roughly the same for Modifies
LASTPIDs compare worse for merges of vCards (2x?)
LASTPIDs just duplicate information you already have.

So why the heck do it?

dgc

> Sent: Saturday, July 26, 2008 1:54 PM
> To: Darryl Champagne
> Cc: [email-masked]

> I've got "easier to read and debug". What other reason is there for
Simple summary - it has a lot fewer problems than LASTPIDs.

How about search for the word LASTPID in the emails?  I tried to be fair,
use realistic numbers, and compare the overall issues, but apparently that
made it too long to follow.

Next - the approach for the RFC that I have asked for is to NOT specify an
algorithm.  For most systems, it doesn't matter.  For the ones that it does,
they will do more.  No LASTPIDs, and not my example.  My algorithm was
provided as an example of what I would probably do, and to demonstrate
problems with LASTPIDs.  It is NOT my approach for the RFC.

Finally, I did not discuss positives of any approach that got collisions,
and although they are not terribly negative - they are still negative.  I
did discuss why LASTPIDs got a lot more collisions than my approach (or
almost any random-ish approach), which is definitely a negative.  In other
words - my example is much less negative than LASTPIDs (and is trivial to
bump it an order of magnitude more if that is what you want, while LASTPIDs
will always collide when Meta-data is lost).

The first of those messages specifically compared LASTPID to my suggestion,
to show why LASTPID got more collisions in the typical Add case (roughly 100
times by numbers I considered reasonable or 10x if I took the least
favorable numbers):

----- Quote from first message ----

"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).
"
----- End Quote from first message ----

Now, if you don't like not specifying an approach to picking PIDs, then at
least specify a random number-ish approach (along with the guidance to not
reuse a PID that you delete, at least for a while), because it will be
better than using LASTPID.

So how about this summary:
LASTPIDs compare about 100x worse for collisions in Adds
LASTPIDs compare about the same order of magnitude for Deletes (with my
proposed text)
LASTPIDs compare about the same order of magnitude for Modifies
LASTPIDs compare worse for merges of vCards (you probably have to renumber
at least twice as many PIDs)
LASTPIDs are just duplicates of information that already needs to be figured
out (anything you can figure out with LASTPIDs can also be figured out the
same way you catch the modifies, which LASTPIDs don't help).

So why the heck do it?

dgc