63
possibility is workable, it makes the definition of the basic data structure much more
complicated, and presents a difficult user-interface problem. How should a program indi-
cate that some number of sequential items (substrings in a text, for instance) are in fact
unordered with respect to each other? This option respects exactly the information
available, but complicates the application data model severely, by allowing sequences
that are non-sequential, at least in part.
• Use some arbitrary ordering to resolve the conflict. This option can be implemented as
long as some total order relation between changes can be found. This could be based on
timestamps, in a real-time collaboration situation, possibly supplemented by one of the
many heuristics for choosing unique Ids. For instance, they could be lexicographically
ordered according to a well-defined binary representation. Because such a representation
is likely to be very long, a cryptographic hash of it would serve as well. While a hash al-
gorithm like MD5 (Rivest 1992) can provide only a probabilistic guarantee of uniqueness,
in practice the probability of failure is vanishingly small.
This is not the only time we will use some relatively arbitrary ordering to resolve a con-
flict. Whenever this happens there is only one strong requirement. The ordering chosen must
be calculable by a program given no other information than the two changes in conflict. In
the case of conflicting insertion points, the strategy of using unique Ids meets this require-
ment, but does impose an additional requirement on any implementation: that a strategy be
chosen and implemented to reliably determine such Ids at non-communicating sites.
3.3.2 Point/range conflicts (for all operations)
Since point operations always insert data at the point, there are two basic cases to con-
sider, depending on whether the contents of the range are to be deleted (as by moveand
delete), or duplicated elsewhere (as bycopyandmove). In the case of a range that is being
deleted, there is only one good choice, out of two possibilities: the data inserted at the
point should be ignored, since the deletion has removed the context around the point. Al-
possibility is workable, it makes the definition of the basic data structure much more
complicated, and presents a difficult user-interface problem. How should a program indi-
cate that some number of sequential items (substrings in a text, for instance) are in fact
unordered with respect to each other? This option respects exactly the information
available, but complicates the application data model severely, by allowing sequences
that are non-sequential, at least in part.
• Use some arbitrary ordering to resolve the conflict. This option can be implemented as
long as some total order relation between changes can be found. This could be based on
timestamps, in a real-time collaboration situation, possibly supplemented by one of the
many heuristics for choosing unique Ids. For instance, they could be lexicographically
ordered according to a well-defined binary representation. Because such a representation
is likely to be very long, a cryptographic hash of it would serve as well. While a hash al-
gorithm like MD5 (Rivest 1992) can provide only a probabilistic guarantee of uniqueness,
in practice the probability of failure is vanishingly small.
This is not the only time we will use some relatively arbitrary ordering to resolve a con-
flict. Whenever this happens there is only one strong requirement. The ordering chosen must
be calculable by a program given no other information than the two changes in conflict. In
the case of conflicting insertion points, the strategy of using unique Ids meets this require-
ment, but does impose an additional requirement on any implementation: that a strategy be
chosen and implemented to reliably determine such Ids at non-communicating sites.
3.3.2 Point/range conflicts (for all operations)
Since point operations always insert data at the point, there are two basic cases to con-
sider, depending on whether the contents of the range are to be deleted (as by moveand
delete), or duplicated elsewhere (as bycopyandmove). In the case of a range that is being
deleted, there is only one good choice, out of two possibilities: the data inserted at the
point should be ignored, since the deletion has removed the context around the point. Al-
