150
model provides semantics for asynchronous work, it provides a basic merge facility with well-
defined semantics, thus meeting merge requirement 4.
Requirement 5 is that change information should be easily accessible for an arbitrary por-
tion of a document. This is met by the properties of the addressing function, which enables
the determination of the set of all changes affecting a particular region (or contributing any
data to its contents). This information is also available for any version of the sequence. We
have also seen that it is possible to compare sub-sequences of a document as easily as whole
documents, thus providing fine-grained diff information for arbitrary regions of a sequence.
Requirement 6 asks that changes be commutative, in the sense that they not have an in-
herent order with respect to each other. Strictly speaking, this is true, since Palimpsest op-
erations can be either active or inactive, and order of arrival is never an issue in correctly
interpreting a change. However, as noted in the requirement, some ordering of move
changes is unavoidable (even though it is not temporal). In the model, Palimpsest move op-
erations are ordered relative to each other by an arbitrary priority function. In practice, that
function is most effectively implemented by using the relative positions of the right end-
points of the source regions of the conflicting moves. Despite the fact that this function is
not a temporal ordering, moves do not commute when operational priorities are inter-
changed, just as they would fail to commute in a traditional temporal ordering. The require-
ment for time-independence is met, which enables the transport and timing independence of
Palimpsest-based systems, but the attractive notion of fully re-combinable changes is not
met.
Requirement 7 is for simple, quick conflict tests. While performance is an implementation
issue, the types of inconsistency in Palimpsest models are few: the reference relation might
not be a causal ordering, or there might be two changes with the same destination. Under
the restrictions posed by changes actually being created at particular times, a causal order-
ing failure can only occur for two reasons. It could occur because of a missing change, which
model provides semantics for asynchronous work, it provides a basic merge facility with well-
defined semantics, thus meeting merge requirement 4.
Requirement 5 is that change information should be easily accessible for an arbitrary por-
tion of a document. This is met by the properties of the addressing function, which enables
the determination of the set of all changes affecting a particular region (or contributing any
data to its contents). This information is also available for any version of the sequence. We
have also seen that it is possible to compare sub-sequences of a document as easily as whole
documents, thus providing fine-grained diff information for arbitrary regions of a sequence.
Requirement 6 asks that changes be commutative, in the sense that they not have an in-
herent order with respect to each other. Strictly speaking, this is true, since Palimpsest op-
erations can be either active or inactive, and order of arrival is never an issue in correctly
interpreting a change. However, as noted in the requirement, some ordering of move
changes is unavoidable (even though it is not temporal). In the model, Palimpsest move op-
erations are ordered relative to each other by an arbitrary priority function. In practice, that
function is most effectively implemented by using the relative positions of the right end-
points of the source regions of the conflicting moves. Despite the fact that this function is
not a temporal ordering, moves do not commute when operational priorities are inter-
changed, just as they would fail to commute in a traditional temporal ordering. The require-
ment for time-independence is met, which enables the transport and timing independence of
Palimpsest-based systems, but the attractive notion of fully re-combinable changes is not
met.
Requirement 7 is for simple, quick conflict tests. While performance is an implementation
issue, the types of inconsistency in Palimpsest models are few: the reference relation might
not be a causal ordering, or there might be two changes with the same destination. Under
the restrictions posed by changes actually being created at particular times, a causal order-
ing failure can only occur for two reasons. It could occur because of a missing change, which
