82
ticular change from the set representing the state corresponding to the user’s “current ver-
sion”. Real-time collaboration could be achieved by a group of processes each keeping a sin-
gle change set representing the current version, and broadcasting new changes to the oth-
ers. The distribution algorithm then determines the ultimate level of consistency achieved
by the system, independently of the data model, since order of arrival will not affect the
final results.
4.2.1 Changes and change sets
The elements of a change set are of four types: insertion, deletion, move and copy. Each
change cin a set has a unique identifier. Two changes may be identical in every property
except their ID (this occurs when two authors make the same correction). Formally, we rep-
resent IDs as elements of a set Id, and a change as a tuple(i, c)
where iis an ID, andcis the
rest of the information about the actual operation represented by the change. Changes may
be written without explicit IDs, where it will not cause confusion. The function Id(c)gives
the ID of a given change c, andChange(I)gives the change with IDI.
The following notations are used to identify the action taken by a change, the possible
values of cin a change tuple(I, c). I[a, s]represents the insertion of a finite sequence of
items (s) at a location given by the addressa.D[a
1 , a
2 ]represents the deletion of all items
whose addresses fall between a
1 and a
2 . M[a
1 , a
2 , d]represents the movement of the subse-
quence with addresses from a
1 …a
2 , inclusive, to the addressd. C[a
1 , a
2 , d]represents a dy-
namic copy that duplicates the subsequence with addresses from a
1 …a
2 ,inclusive, to the
address d.
4.2.2 The structure of Palimpsest addresses
Palimpsest addresses represent the locations of data, by the IDs of the changes that cre-
ated that data and have affected its position. The addresses have the general form discussed
in Section 3.4.3.
ticular change from the set representing the state corresponding to the user’s “current ver-
sion”. Real-time collaboration could be achieved by a group of processes each keeping a sin-
gle change set representing the current version, and broadcasting new changes to the oth-
ers. The distribution algorithm then determines the ultimate level of consistency achieved
by the system, independently of the data model, since order of arrival will not affect the
final results.
4.2.1 Changes and change sets
The elements of a change set are of four types: insertion, deletion, move and copy. Each
change cin a set has a unique identifier. Two changes may be identical in every property
except their ID (this occurs when two authors make the same correction). Formally, we rep-
resent IDs as elements of a set Id, and a change as a tuple(i, c)
where iis an ID, andcis the
rest of the information about the actual operation represented by the change. Changes may
be written without explicit IDs, where it will not cause confusion. The function Id(c)gives
the ID of a given change c, andChange(I)gives the change with IDI.
The following notations are used to identify the action taken by a change, the possible
values of cin a change tuple(I, c). I[a, s]represents the insertion of a finite sequence of
items (s) at a location given by the addressa.D[a
1 , a
2 ]represents the deletion of all items
whose addresses fall between a
1 and a
2 . M[a
1 , a
2 , d]represents the movement of the subse-
quence with addresses from a
1 …a
2 , inclusive, to the addressd. C[a
1 , a
2 , d]represents a dy-
namic copy that duplicates the subsequence with addresses from a
1 …a
2 ,inclusive, to the
address d.
4.2.2 The structure of Palimpsest addresses
Palimpsest addresses represent the locations of data, by the IDs of the changes that cre-
ated that data and have affected its position. The addresses have the general form discussed
in Section 3.4.3.
