Subject: Re: Proposed change to iCal (was RE: Adding more unique identifiers)

From: John Stracke <[email-masked]>
Date: Wed, 08 Aug 2001 12:56:03 +0100

Roger D wrote:

> As currently written, though using them is optional, they do have implementation consequences for all implementors, since even if a calendar system does not choose to add UIDs or PUIDs to things that don't have them in RFC 2445, it MUST store and return them if replying to a request which contained them. Are people happy with this extra requirement?

No.  I have to be conservative about adding new field to my database; and the purpose of these new IDs was not clear to me.

--
/==============================================================\
|John Stracke    | http://www.ecal.com |My opinions are my own.|
|Chief Scientist |=============================================|
|eCal Corp.      |But this one goes to 11x.                    |
[email-masked]|                                             |
\==============================================================/

---

From: Roger D <[email-masked]>
Date: Tue, 14 Aug 2001 18:27:42 -0700

[email-masked] wrote:

> Roger D wrote:
>>As currently written, though using them is optional, they do have

>>implementation consequences for all implementors, since even if a

>>calendar system does not choose to add UIDs or PUIDs to things that

>>don't have them in RFC 2445, it MUST store and return them if

>>replying to a request which contained them. Are people happy with

>>this extra requirement?
> 
> No.  I have to be conservative about adding new field to my database;

How do you store and return unchanged X-PARAMs and X-PROPs? If you 
don't, I believe you are in breach of the standard; if you do, why can't 
you just use the same mechanism for storing these?

 > and the purpose of these new IDs was not clear to me.

OK. Here is the basic problem:

Suppose a user is organizing a meeting. They have several different CUAs 
that they are using to make modifications to the meeting (say a desktop 
machine, a laptop, a PDA, a website or voice interface attached to the 
calendar server), and possibly one or more other individuals are 
entitled to make changes on their behalf and are doing so using yet 
other CUAs. Particularly given that some of these may allow the user to 
work in offline mode on a cached copy of the data, there is no guarantee 
that the various changes they make in these CUAs will reach the server 
in the correct order. We don't just want to bump the sequence number 
every time anything is changed and discard changes that arrive out of 
order with a stale sequence number, since that would a) force invitees 
to re-RSVP to a meeting even if nothing major has changed about it, and 
b) enforce throwing away what may be perfectly good changes that we 
could have successfully figured out how to merge. So it is a reasonable 
aim for a server to attempt to merge changes from coming in from 
different sources: if e.g. if one change changes the SUMMARY and another 
changes one of the VALARMs, they can reasonably be merged. (But if both 
change the description, we are going to have decide which one of them we 
have overwrite the other, or else involve the user to help use resolve 
the merge.)

However, there is a problem to doing this: currently there are a number 
of different entities attached to a meeting (e.g. ATTACHments, 
RESOURCES, VALARMs, CATEGORIES) for which there can be multiple entities 
of a certain type attached to a meeting (so an individual one is not 
uniquely identified by the UID of the meeting) and that (unlike an 
ATTENDEE) do not have an inherent unique identifier. This makes trying 
to merge changes to these items extremely difficult for the server: if 
you started with list {a, b} and sent back {c, d}, did you intend to 
delete a and b and add c and d, or to change a into c and b into d, or 
to change a into d and b into c, or to delete a, add b, and change c 
into d, etc.? How should this be merged with another change that started 
with {a, b} and returned {b} (presumably they just deleted a, but even 
this is not completely clear).
If the objects had a unique identifier this would be resolved, since 
changing a into b would keep the same unique identifier, while deleting 
a and adding b would create a new one. Then the merge rule is simple:
identify objects by their unique ID, and only if to changes change the 
same object do you need to worry about resolving the order in which the 
changes should be applied.

A more direct inspiration for us to want to do this is that we are using 
a format derived from iCal on our internal data bus inside our CUA, and 
different pieces of the application (the GUI, the connection to the 
server) could me making unsynchronized changes to details of the same 
event: we need some way of automatically merging these changes in our 
data bus, and we can't afford to unnecessarily bump the sequence number, 
discard changes, or involve the user. Thus, at least internally, we need 
to add more unique identifiers than the iCal standard has. Since our 
server and client share codebase, it is thus very tempting to add them 
in the server too, and to transmit them between the client and server 
and use them as outlined in the previous paragraph.

A general rule of good data structure design is that any item of data 
should have a unique identifier. Currently iCal breaks that:

a) at the component level: a VALARM has no unique identifier, a 
VTIMEZONE is identified only by its TZID which is not guaranteeably 
unique, and the STANDARDC and DAYLIGHTC components in a VTIMEZONE are 
best identified by their DTSTART but again this is not guaranteed to be 
unique. My proposal was that a UID be allowed as a property of each of 
these, and that at least for VALARM the standard recommend that one be 
generated when the VALARM is generated.

b) at the property level: ATTACH, CATEGORIES, COMMENT, CONTACT, 
DAYLIGHTC, EXRULE, FREEBUSY, RSTATUS, RELATED, RESOURCES, RRULE, 
STANDARDC, TZNAME and X-PROP, and possibly also DESCRIPTION for 
VJOURNALs (the standard disagrees with itself) can occur multiple times 
but have no inherent unique identifier (unlike ATTENDEE, and arguably 
EXDATE and RDATE). My proposal was to add a PUID unique identifier 
property parameter to these properties to allow them to be uniquely 
identified.

 From the lack of response on the list to my previous suggestion, I get 
the impression that many other people have found some other way of 
resolving this data merging issue, and I would be interested in know 
what approach(es) they took.

If no one wants these added to the standard, we will just make them 
X-PROPerties and X-PARAMeters and use them internally in our CUA and 
server and between our CUA and our server. But that means we can't be 
smart about merging changes if they come from some other CUA (say one on 
a PDA). To get full interoperability, they need to be in the standard. 
Obviously we can have interoperability without everyone adding UIDs and 
PUIDs that they don't use in their CUA: they can be optional, and if the 
CUA that the event was first created on didn't add them the server can 
add them later if it wishes (the reverse, a server not using them but a 
CUA adding them is more problematic: what if two different CUAs both 
issue different unique identifiers to the same item?). However, if a CUA 
that doesn't use them is communicating with a server that does put UIDs 
on VALARMs, and/or PUIDs on certain properties, it does need to retain 
them and return them on a changed version of the event, not strip them 
off and return a changed VEVENT with pieces in it that are no longer 
uniquely identified, otherwise we are back at square one.

--Roger

---

From: John Stracke <[email-masked]>
Date: Wed, 15 Aug 2001 09:55:10 -0400

Roger D wrote:

> [email-masked] wrote:
>
>> I have to be conservative about adding new field to my database;
>
> don't, I believe you are in breach of the standard;

What standard? iCalendar is a data format; it is silent about what you 
do with the data.  CAP could attempt to specify that x-params have to 
come back unchanged; but, at present, it doesn't, because it barely 
specifies behavior at all.  If such behavior is added to a future 
version of the I-D, I will oppose it, because it would require me to 
have an open-ended database schema, which would be difficult or 
impossible to tune for performance.

> OK. Here is the basic problem: 

[...]

I dunno; it sounds to me like an edge case.  It is a problem, but a 
solved one (I think): that's what sync engines are for.

-- 
/==============================================================\
|John Stracke    | http://www.ecal.com |My opinions are my own.|
|Chief Scientist |=============================================|
|eCal Corp.      |"No, no, that's *not* a boat, that's Queen   |
[email-masked]|Victoria."                                   |
\==============================================================/

---

From: Alan Davies <[email-masked]>
Date: Wed, 15 Aug 2001 10:19:58 -0400

At 06:27 PM 14/08/2001 -0700, Roger D wrote:
 > [...] e.g. if one change changes the SUMMARY and another changes one of
 > the VALARMs, they can reasonably be merged. (But if both change the
 > description, we are going to have decide which one of them we have
 > overwrite the other, or else involve the user to help use resolve the 
merge.)

 > [...] This makes trying to merge changes to these items extremely difficult
 > for the server: if you started with list {a, b} and sent back {c, d}, did
 > you intend to delete a and b and add c and d, or to change a into c and b
 > into d, or to change a into d and b into c, or to delete a, add b, and 
change
 > c into d, etc.? How should this be merged with another change that 
started with
 > {a, b} and returned {b} (presumably they just deleted a, but even this 
is not
 > completely clear).

I agree.

 > If the objects had a unique identifier [...] Then the merge rule is simple:
 > identify objects by their unique ID, and only if to changes change the same
 > object do you need to worry about resolving the order in which the changes
 > should be applied.

How would the PUIDs help a CS to solve the problem that you stated and I quoted
above, where two CUAs modify the same list? It still doesn't know which 
combination
of b, c and d to keep without user interaction. Can you give an example of
a CS correctly performing a merge with a conflict that couldn't have been
resolved without PUIDs?

A CS also has to rely on both CUAs interpreting this sentence in the
same way: "changing a into b would keep the same unique identifier".
What exactly does "changing a into b" mean?

--Alan

---

From: Roger D <[email-masked]>
Date: Thu, 16 Aug 2001 18:20:54 -0700

[email-masked] wrote:

> I dunno; it sounds to me like an edge case.

Data integrity if the user uses more than one CUA is an edge case? I 
don't regard it as such: plenty of people have at least two out of: work 
desktop, home desktop, laptop, PDA, direct website connection to server,
voice access to server.

> It is a problem, but a 

That's exactly what I'm tring to do: write a synch engine. The iCal 
standard is inadequate to the task, since it contains lists on anonymous 
elements.

--Roger

---

From: Roger D <[email-masked]>
Date: Thu, 16 Aug 2001 19:10:06 -0700

[email-masked] wrote:

>> into d, or to change a into d and b into c, or to delete a, add b, and change
>> c into d, etc.? How should this be merged with another change that started with
>> {a, b} and returned {b} (presumably they just deleted a, but even this is not
>> completely clear).

...

> above, where two CUAs modify the same list? It still doesn't know which combination

1) A VEVENT is somehow created on the server with two RESOURCES: 
"flipchat" and "projector". Each has been issued a PUID.

2) A copy of the VEVENT is downloaded to a CUA on the user's laptop, 
where it is cached.

3) A copy of the VEVENT is downloaded to another CUA on the PDA of the 
user's secretary (who has "act on behalf" of privileges for the user), 
where it is cached.

4) Working offline (his radio modem has temporarily dropped the 
connection due to poor reception on the train he's on), the user deletes 
"projecter" since he recalls that the location they will be using has 
one built in and so it doesn't need to be arranged specially. Later he 
adds "microphone and PA system" (this gets issued a new PUID), since he 
recalls that the ones installed in the location are unreliable.

5) Also working offline (waiting at a bus terminal), the user's 
secretary corrects the misspelling of "flipchat" to "flipchart" and 
"projecter" to "projector". Since these are  modification of the 
existing items, her CUA retains the same PUIDs for them.

6) At some point and in some order, the user's laptop and the 
secretary's PDA get resynched with the server.

a) Suppose the secretary's PDA synchs first. The server sees an incoming 
item with the same sequence number as it's version (since none of these 
changes were large enough to require a new sequence number). Where it has:
{"flipchat"[PUID=1], "projecter"[PUID=2]}
the incoming version has:
{"flipchart"[PUID=1], "projector"[PUID=2]}
The server knows that this is a change of the name of both items, and 
updates itself to:
{"flipchart"[PUID=1], "projector"[PUID=2]}
Then the laptop synchronizes. The server knows that the version that the 
laptop downloaded was:
{"flipchat"[PUID=1], "projecter"[PUID=2]}
What is returned is:
{"flipchat"[PUID=1], "microphone and PA system"[PUID=3]}
The server notes that they did not modify the item with PUID=1, so it 
retains latest version, i.e. the secretary's correction of this to 
"flipchart". However, they did delete the item with PUID=2, so the 
secretaries corrected version "projector" is deleted, and they added a 
new item with a new PUID, "microphone and PA system".
The system thus sets itself to:
{"flipchart"[PUID=1], "microphone and PA system"[PUID=3]}

b) Suppose the user's laptop synchs first. The server sees an incoming 
item with the same sequence number as it's version (since none of these 
changes were large enough to require a new sequence number). Where it has:
{"flipchat"[PUID=1], "projecter"[PUID=2]}
the incoming version has:
{"flipchat"[PUID=1], "microphone and PA system"[PUID=3]}
The server updates itself to this.
Then the secretary's PDA synchronizes. The server knows that the version 
that the PDA downloaded was:
{"flipchat"[PUID=1], "projecter"[PUID=2]}
What is returned is:
{"flipchart"[PUID=1], "projector"[PUID=2]}
The server accepts the update of item with PUID=1, but discards that of 
the item with PUID=2 since that item has been deleted.
The system thus sets itself to:
{"flipchart"[PUID=1], "microphone and PA system"[PUID=3]}

Thus, regardless of the order the changes arrive in, the server merges 
them and ends up with the same result, which is different from (and 
superior to) either of the versions that were returned to it. I have 
been unable to think of any way of producing this result without using a 
unique identifier. iCal recognizes the importance of unique identifiers 
and puts UIDs on many items in the standard: it just doesn't go far enough.

 > What exactly does "changing a into b" mean?

For this to be useful the user interfaces of both CUAs need to 
distinguish between "delete 'projecter', then as a later operation add 
'microphone and PA system' [which gets a new PUID]" and "transform 
'flipchat' into 'flipchart' [keeping the same PUID]". This is a common 
distinction to make in graphical user interfaces (e.g. deleting one file 
and later creating another is a different operation from simply renaming 
the file).

Obviously there may be CUAs that don't make this distinction, or that 
don't retain and return the PUID. If so, merging their changes into the 
others will work just as badly as things do currently. But to the extent 
that the server and all CUAs involved maintain and correctly use PUIDs, 
the result will be more accurate merging of changes coming from 
different sources.

--Roger