87
While conflicted change sets are always problematic they naturally result from the merge
of some minimally consistent change sets. Such situations are exactly the ones in which syn-
tactic consistency is not preserved, since two subsequences cannot be inserted into a se-
quence at exactly the same position. In distributed implementations, communication errors
could lead to failure to transmit some changes. In this case, automatic merge would produce
results that are not causal sets.
4.3 A-sequences and P-sequences
A P-sequence represents a particular state of a Palimpsest sequence, as defined by a set of
changes. P-sequences have an addressing structure as described above and discussed in
Chapter 3, and are defined as a particular type of A-sequence. A-sequences (short for ad-
dressable sequences) represent the notion of a sequence with an explicit address space, iden-
tifying one or more gapsbetween sequence items.
The normal mathematical representation of a sequence of length n is as a function from
the interval 1…n (or 0…n-1 ) from positions in the sequence to values at positions in the
sequence. A-sequences have a similar definition, but with an address space other than the
natural numbers. An A-sequence, X,is a function (called thecontentsfunction)C
X (a
1 , a
2 ),
where a
1 anda
2 are drawn from a totally ordered set(A
X , <)of addresses. The values ofC
x are
sequences of items drawn from a set Vof values. There are no restrictions on the setV,as its
elements are application-specific data. The sequence C
X (a
1 , a
2 ) is the sequence of values
stored between positions a
1 anda
2 ofX.The index functionI
X (a), fora e A
x , returns a num-
ber from 0…size(A
X )-1,representing the position ofainX. The inverseP
X (n),returns then-
th address of a given A-sequence. C
x must satisfy certain properties:
1. C
X (a, a) = L(The null string)
2. C
X (a
1 , a
2 ) = L(if a
2 < a
1 )
While conflicted change sets are always problematic they naturally result from the merge
of some minimally consistent change sets. Such situations are exactly the ones in which syn-
tactic consistency is not preserved, since two subsequences cannot be inserted into a se-
quence at exactly the same position. In distributed implementations, communication errors
could lead to failure to transmit some changes. In this case, automatic merge would produce
results that are not causal sets.
4.3 A-sequences and P-sequences
A P-sequence represents a particular state of a Palimpsest sequence, as defined by a set of
changes. P-sequences have an addressing structure as described above and discussed in
Chapter 3, and are defined as a particular type of A-sequence. A-sequences (short for ad-
dressable sequences) represent the notion of a sequence with an explicit address space, iden-
tifying one or more gapsbetween sequence items.
The normal mathematical representation of a sequence of length n is as a function from
the interval 1…n (or 0…n-1 ) from positions in the sequence to values at positions in the
sequence. A-sequences have a similar definition, but with an address space other than the
natural numbers. An A-sequence, X,is a function (called thecontentsfunction)C
X (a
1 , a
2 ),
where a
1 anda
2 are drawn from a totally ordered set(A
X , <)of addresses. The values ofC
x are
sequences of items drawn from a set Vof values. There are no restrictions on the setV,as its
elements are application-specific data. The sequence C
X (a
1 , a
2 ) is the sequence of values
stored between positions a
1 anda
2 ofX.The index functionI
X (a), fora e A
x , returns a num-
ber from 0…size(A
X )-1,representing the position ofainX. The inverseP
X (n),returns then-
th address of a given A-sequence. C
x must satisfy certain properties:
1. C
X (a, a) = L(The null string)
2. C
X (a
1 , a
2 ) = L(if a
2 < a
1 )
