65
bility (and preservation of the range concept) is gained when insertion operations are
propagated as fully as possible.
3.3.3 Range/range conflicts
In cases where two affected regions overlap, the significant question is how to order the
effects on the two respective ranges. There are several significant cases:
1. One of the changes is a deletion operation. Regardless of what the other operation is,
the deletion should take priority. In the case of two deletion operations, both can
take effect without conflict.
2. Both changes are copy operations. In this case they can take effect without conflict,
just as in the deletion case.
3. One or both changes are move operations. In this complex case, the conflict is hard
to resolve. It is possible to allow both changes to take simultaneous effect, or to or-
der them with respect to one another.
Cases one and two really need no further discussion, but case three has a number of
points of interest. The first resolution possibility to consider is simultaneous effect. For
move/copy, this is quite reasonable. This is essentially the same as ordering the move before
the copy; the copy will see the results of the move, because of the move’s deletion of its
source range. For a move/move conflict, the results are not so intuitive: whatever region is
shared by the two move operations will be deleted for bothof them. This counterintuitive
result (that conflicting move operations can delete data) makes this a bad solution.
If the two changes need to be ordered with respect to each other, there are a variety of
possible solutions (any method of creating a total order on changes will do). The most obvi-
ous method to consider is temporal ordering. While this is probably good in some real-time
situations, the work required to calculate temporal ordering in a distributed system is sig-
nificant, and a fallback method must be in place for the unlikely event that two changes
were made at precisely the same time. Since it is hard to determine in a distributed system,
bility (and preservation of the range concept) is gained when insertion operations are
propagated as fully as possible.
3.3.3 Range/range conflicts
In cases where two affected regions overlap, the significant question is how to order the
effects on the two respective ranges. There are several significant cases:
1. One of the changes is a deletion operation. Regardless of what the other operation is,
the deletion should take priority. In the case of two deletion operations, both can
take effect without conflict.
2. Both changes are copy operations. In this case they can take effect without conflict,
just as in the deletion case.
3. One or both changes are move operations. In this complex case, the conflict is hard
to resolve. It is possible to allow both changes to take simultaneous effect, or to or-
der them with respect to one another.
Cases one and two really need no further discussion, but case three has a number of
points of interest. The first resolution possibility to consider is simultaneous effect. For
move/copy, this is quite reasonable. This is essentially the same as ordering the move before
the copy; the copy will see the results of the move, because of the move’s deletion of its
source range. For a move/move conflict, the results are not so intuitive: whatever region is
shared by the two move operations will be deleted for bothof them. This counterintuitive
result (that conflicting move operations can delete data) makes this a bad solution.
If the two changes need to be ordered with respect to each other, there are a variety of
possible solutions (any method of creating a total order on changes will do). The most obvi-
ous method to consider is temporal ordering. While this is probably good in some real-time
situations, the work required to calculate temporal ordering in a distributed system is sig-
nificant, and a fallback method must be in place for the unlikely event that two changes
were made at precisely the same time. Since it is hard to determine in a distributed system,
