Deletion of Lines of Text

Deleted lines need to be stored as if they were modified lines, with a marker that they are no longer visible. If they were not stored as actual objects, then they may be re-asserted by sites which have missed seeing the deletion event. Unfortunately it is necessary for deleted line ID's and deletion times to actually be transmitted and stored at all sites to prevent unintentional re-assertion of deleted lines after the deleting site has left the conference.

If an entire block of text has been deleted, sites only need hold the ID and deletion time of the block - the holding of information of lines within the block is unnecessary.

To prevent the re-assertion of lines or blocks after deletion when a network partition is resolved, it is even necessary to send deleted block and line ID's and timestamps to new sites joining the conference, so that they can continue to suppress re-assertion of the deleted line or block after all the other members of this partition have left the conference.

To prevent unnecessary usage of bandwidth and memory, line and block IDs could be re-used for new lines and blocks. However, this is dangerous as a deletion event and the subsequent re-use of the line ID in one partition, followed by the modification of the original line in another partition can lead to undesired consequences. It would be possible to consider schemes where a line ID can only be re-used in a different block from the one it was previously used in, and thus the line's block id field can be used for collision detection, but if the site originating the ID is no longer reachable, it is far from obvious who can resolve the conflict without introducing further complications. Thus in NTE, we have not attempted to implement any ID re-use system.

The most significant design decision here concerns the effects of network partitioning - if a user at a site in one partition deletes a line, and subsequently another user in the other partition modifies the line, we have two choices when the partition is resolved:

• Rely only on modification time (i.e. treat deletion as just another modification that can be rectified later if required)
• Impose an ordering on operations such that deletion is of ``higher order'' than normal modification, such that deletion always prevails over modification.

If we treat deletion as modification, then when several neighbouring lines are deleted in one partition, and one of the middle lines is subsequently modified in the other partition, a single line would be re-asserted with no surrounding context. There are mechanisms we could employ to deal with this, but they tend to add unnecessary complexity, and generally are less natural to users.

If we treat deletion as a higher order operation, then a different scenario causes potential problems - a line can be split into two lines in one partition (one modified line and one new one), and subsequently deleted in another partition, leading to only half a line remaining after the split when the partitioning is resolved.

We took the decision that deletion is a higher order operation, as this provides us with a mechanism that is irrespective of causal ordering in a partitioned network, and this causal ordering independence provides a mechanism which we can utilise to achieve internally consistent global consistency.

Thus the problem above where a line is split in two (a ``newline'' is added to the middle of the line) can thus be resolved by deleting the line we wish to split and inserting two new lines in its place. This achieves internal consistency because even if the line split in one partition is modified or deleted in the other partition, the deletion operator overrides the modification operator, and the two new lines then take its place. Of course if a line is split in both partitions, then we now get both versions of the line after partition resolution, with no globally consistent view of the line ordering in the block. Thus we've moved the problem to that of effectively simultaneous insertion of lines. However, effectively simultaneous insertion is a detectable situation, as we shall show below.

In fact to achieve inconsistency detection, there is one further requirement with respect to deleted lines; they must not only be kept at all sites to prevent re-assertion of the line from a site that missed the deletion, but they must also be kept in their original place in the list of lines at each site. Thus, a line preceding a deleted line must still be transmitted with its "next line" field indicating the deleted line. This is necessary so that simultaneous insertion is a detectable situation.