69
space, labeled with the contents at that point in the space. Struck-through items are not
actually part of the resulting sequence, but are shown because their addresses still exist.
Grayed text is text that is copied from some other location. Implicit in the diagram is the
existence of a change, not shown, which inserted the original string “ABCDEF” before the
other edits. The reason to track these addresses is that they provide the needed information
to forward the effects of a change that may have been made independently of the rear-
rangement in question.
Each location in the global address space is identified in terms of the operations that
have affected it. Before pursuing the details of conflict resolution and what addresses should
be preferred in achieving meaningful results, it may help to look at a few examples of what
addresses look like. Assuming that the original string in Figure 3.2 was created by a single
insertion with ID I1, there would be 7 addresses defined on account of the existence ofI1:
(I1, 0), …, (I1, 6) . The addition of the copy operation C2would create 4 more new ad-
dresses: (C2.I1, 0), …, (C2.I1, 3) . Each address is specified in terms of the changes that di-
rectly affect its content.
3.4.2 The interaction of operation types and addressing structure
The basic idea of keeping a supra-temporal record of the evolution of an entire data
structure and selecting relevant parts of its history on demand is an old one (at least for se-
quential files modified by insertion and deletion operations). This is the main implementa-
tion strategy used in SCCS (Rochkind 1975),one of the earliest modern configuration sys-
tems. But the introduction of operations like moveandcopythat rearrange and duplicate
data creates a new problem: how to address data that may logically appear in more than one
place (depending, of course, on user choices of view and version). Consider the simple opera-
tions in Figure 3.2. The subsequence “ABC” appears twice in the address space underlying
each string in the figure. One important question is which of the two possible addresses for
each position within that subsequence should be used in representing other operations.
space, labeled with the contents at that point in the space. Struck-through items are not
actually part of the resulting sequence, but are shown because their addresses still exist.
Grayed text is text that is copied from some other location. Implicit in the diagram is the
existence of a change, not shown, which inserted the original string “ABCDEF” before the
other edits. The reason to track these addresses is that they provide the needed information
to forward the effects of a change that may have been made independently of the rear-
rangement in question.
Each location in the global address space is identified in terms of the operations that
have affected it. Before pursuing the details of conflict resolution and what addresses should
be preferred in achieving meaningful results, it may help to look at a few examples of what
addresses look like. Assuming that the original string in Figure 3.2 was created by a single
insertion with ID I1, there would be 7 addresses defined on account of the existence ofI1:
(I1, 0), …, (I1, 6) . The addition of the copy operation C2would create 4 more new ad-
dresses: (C2.I1, 0), …, (C2.I1, 3) . Each address is specified in terms of the changes that di-
rectly affect its content.
3.4.2 The interaction of operation types and addressing structure
The basic idea of keeping a supra-temporal record of the evolution of an entire data
structure and selecting relevant parts of its history on demand is an old one (at least for se-
quential files modified by insertion and deletion operations). This is the main implementa-
tion strategy used in SCCS (Rochkind 1975),one of the earliest modern configuration sys-
tems. But the introduction of operations like moveandcopythat rearrange and duplicate
data creates a new problem: how to address data that may logically appear in more than one
place (depending, of course, on user choices of view and version). Consider the simple opera-
tions in Figure 3.2. The subsequence “ABC” appears twice in the address space underlying
each string in the figure. One important question is which of the two possible addresses for
each position within that subsequence should be used in representing other operations.