Effectively Simultaneous Insertion of Lines

Effectively simultaneous modification of a single line always results in a block that is internally consistent and the document in a globally consistent state. We've shown that if deletion is treated as a higher order operation than deletion, then combinations of moving, deletion line splitting and so forth can be dealt with, but with one potential side-effect - all these operations can result in effectively simultaneous insertion of lines.

Effectively simultaneous insertion of lines is a slightly harder problem than the problems discussed above, because it not only results in a document that is not internally consistent (we have two copies of essentially the same line or lines) but also the document is not globally consistent either (different sites can have different views of the document). This occurs because two (or more) lines each have the same neighbouring lines. The problem can be detected at all sites, because a set of lines is received that should fit in the same place in a block as a set of lines we already have.

At this point the choices we made above, about deletion being a higher order operation than modification but that deleted lines are retained, and moving of lines being treated as deletion and re-insertion, ensure that if a newly received line has a particular previous line, then there are only three choices for where the next line is:

  

Figure 8.7: Simultaneous Insertion is a Detectable Situation

  

Figure 8.8: Simultaneous Deletion and Insertion - no inconsistency

  

Figure 8.9: Simultaneous Deletion and Insertion resulting in inconsistency

1.

There is no next line. This line is the end of the block.

2.

We have seen the next line, and it is later in the block (possibly deleted).

3.

We have not seen the next line.

If we have not seen the next line, then we know we have a potential inconsistency, and thus we should not display the received line until we have the next line too. We wait until the line's ``next line'' arrives, and again go through this process again. If the next line is a line we've seen, or the end of the block, then we have enough information to know whether we have a problem or not. We can therefore treat a connected set one or more new lines as if they were a single line - if the line in our existing block following the ``previous line'' of the new data is not the same as the ``next line'' of the new data, then we have an inconsistency which must be resolved (see figure 8.7); otherwise we can unambiguously display the lines.

Now, so long as we keep deleted lines in their original place in the block and simply don't display them (see figures 8.8 and 8.9 for examples), and so long as we treat moving as deletion and subsequent insertion, then there is only one way such an inconsistency could occur - that alternative new lines were inserted effectively simultaneously. Thus the question comes down to which of the two sets of lines to keep and which to delete. So long as this matter is resolved globally consistently, then global consistency can be restored to the block. In fact it is not quite so simple as this, because if we delete one version of the lines, we must ensure that the block is globally consistent including the position of the deleted lines or we may not be able to detect further inconsistencies at all sites. However, we do not care about the order of a set on consecutively deleted lines, so instead of deleting one of the two alternative sets of lines, we must actually delete both alternative sets of lines and re-insert one of them again.

The choice of which alternative set of lines to retain can be made automatically (by the ``current site'') or it can be made clear to the users that there is a problem that requires resolution. Either way, if more than one site attempts to resolve the conflict, the cycle is simply repeated again.