88
These ensure that each address corresponds to no more a single element from Vand that
zero- or negative-length address ranges contain only the null string. They do not ensure
that every range of addresses has any content, because an A-sequence can contain addresses
for deleted data that does not appear in the final sequence. We will omit the subscript iden-
tifying the particular A-sequence when only one sequence is under discussion.
4.3.1 P-sequences
P-sequences formalize how changes are assembled into a set of ordered addresses related
to particular sequences of values. The Palimpsest addressing scheme assigns addresses in a
way that admits of other uses, as well. The structure of the address space enables the deter-
mination of what data is common to two P-sequences. Given two P-sequences it is possible to
determine, by inspection, what data was duplicated by copy operations or moved by move
operations, and what original insertion operation initially added any particular value to the
sequence. P-sequences are defined for minimally consistent change sets, but I shall note we
dependencies on minimal consistency, and to what extent that restriction can be relaxed.
The P-sequence P
S has three components:
1. A total ordering relation,<
SA , on A’(S) .
2. The set of addressesA’(S)determined by a set of changesS.
3. A functionC
S (a
1 , a
2 )that returns a subsequence for a P-sequence range indicated by
2 addresses in A’(S) .
The P-sequence P
S is an A-sequence with addresses A’(S), contents function C
S ,and ad-
dress ordering <
SA . The ordering of a P-sequence is what determines the final linear structure
of the addresses in the sequence, and allows the enumeration of its contents. It is <
SA that
orders the addresses created by a minimally consistent change set.
4.3.2 The P-sequence address ordering
In this section the address ordering, <
sa is defined. This definition and the following ones
are a bit tricky, since the actual addresses in a P-sequence are the changes in A’(S) . The ef-
These ensure that each address corresponds to no more a single element from Vand that
zero- or negative-length address ranges contain only the null string. They do not ensure
that every range of addresses has any content, because an A-sequence can contain addresses
for deleted data that does not appear in the final sequence. We will omit the subscript iden-
tifying the particular A-sequence when only one sequence is under discussion.
4.3.1 P-sequences
P-sequences formalize how changes are assembled into a set of ordered addresses related
to particular sequences of values. The Palimpsest addressing scheme assigns addresses in a
way that admits of other uses, as well. The structure of the address space enables the deter-
mination of what data is common to two P-sequences. Given two P-sequences it is possible to
determine, by inspection, what data was duplicated by copy operations or moved by move
operations, and what original insertion operation initially added any particular value to the
sequence. P-sequences are defined for minimally consistent change sets, but I shall note we
dependencies on minimal consistency, and to what extent that restriction can be relaxed.
The P-sequence P
S has three components:
1. A total ordering relation,<
SA , on A’(S) .
2. The set of addressesA’(S)determined by a set of changesS.
3. A functionC
S (a
1 , a
2 )that returns a subsequence for a P-sequence range indicated by
2 addresses in A’(S) .
The P-sequence P
S is an A-sequence with addresses A’(S), contents function C
S ,and ad-
dress ordering <
SA . The ordering of a P-sequence is what determines the final linear structure
of the addresses in the sequence, and allows the enumeration of its contents. It is <
SA that
orders the addresses created by a minimally consistent change set.
4.3.2 The P-sequence address ordering
In this section the address ordering, <
sa is defined. This definition and the following ones
are a bit tricky, since the actual addresses in a P-sequence are the changes in A’(S) . The ef-
