57
tion combination. There are only three structural cases to consider, giving a triangular ma-
trix of possibilities, all of which are inherently possible for any system that allows diver-
gence:
• Point-point conflicts.These are all essentially the same, and they all represent a potential
conflict. When more than one insertion is made at the same pointeither an application
conflict must be reported, or the two items must be ordered relative to one another—in
such a way that the same pair of operations will always be ordered the same way.
• Point-range conflicts.These are essentially all of a similar form, with some data being
inserted in a region that is read or affected by another operation. If the range is only
read, no conflict should occur, as the two changes are independent; when both are ac-
tive, the operation that reads the range should receive a result including the added data.
In the case where the range is to be modified by the operation, a semantic conflict is
possible, depending on the effect to be performed on the range. For most operations, the
conflict should be resolved in the same way as in the read-only case. One implication of
this is that the results of an insertion are lost if a range containing the insertion point is
deleted.
• Range-range conflicts.These present varying problems, depending on whether the opera-
tions change the position of contents of the ranges, or whether the operations simply
read the contents of the ranges. In the case of overlaps where both operations merely
read the contents of the ranges, there is no inherent conflict. But in cases where even
one of the ranges is affected by one of the operations, an inherent conflict exists. If the
application does not disallow the combination, the system must be able to order the op-
erations in order to determine what effect occurs in the region of the overlap. Even more
than in the case of multiple insertions at a single point, this is a structural situation
where the system must make a decision about how to order changes. Furthermore, this
tion combination. There are only three structural cases to consider, giving a triangular ma-
trix of possibilities, all of which are inherently possible for any system that allows diver-
gence:
• Point-point conflicts.These are all essentially the same, and they all represent a potential
conflict. When more than one insertion is made at the same pointeither an application
conflict must be reported, or the two items must be ordered relative to one another—in
such a way that the same pair of operations will always be ordered the same way.
• Point-range conflicts.These are essentially all of a similar form, with some data being
inserted in a region that is read or affected by another operation. If the range is only
read, no conflict should occur, as the two changes are independent; when both are ac-
tive, the operation that reads the range should receive a result including the added data.
In the case where the range is to be modified by the operation, a semantic conflict is
possible, depending on the effect to be performed on the range. For most operations, the
conflict should be resolved in the same way as in the read-only case. One implication of
this is that the results of an insertion are lost if a range containing the insertion point is
deleted.
• Range-range conflicts.These present varying problems, depending on whether the opera-
tions change the position of contents of the ranges, or whether the operations simply
read the contents of the ranges. In the case of overlaps where both operations merely
read the contents of the ranges, there is no inherent conflict. But in cases where even
one of the ranges is affected by one of the operations, an inherent conflict exists. If the
application does not disallow the combination, the system must be able to order the op-
erations in order to determine what effect occurs in the region of the overlap. Even more
than in the case of multiple insertions at a single point, this is a structural situation
where the system must make a decision about how to order changes. Furthermore, this
