101
Existing versions are edited by a user, and the results are added to the version graph by a
user operation. Versions are almost always stored in a single logical repository, although it
may be physically distributed across multiple machines. Access control is provided so that
only versions without successors can be updated, adding new nodes to the graph, and to
prevent users from inadvertently creating unwanted versions. When non-tree structured ver-
sion graphs are supported, they are created by user-executed mergeoperations. A merge op-
eration creates a new state that is a descendent of more than one node in the version graph.
The structure of change histories is the other factor in determining how changes interact,
and how conflicts arise and are resolved. Table1.1 (in Section1.4) lists the usual user-visible
history structures in terms of the topology of version graphs. Any general infrastructure
should be able to support these models. One key characteristic of the notions of serializabil-
ity that we are replacing is that changes are temporally ordered in a linear way. When diver-
gent editing occurs, a fork in the history also occurs, and one concern is whether and how to
merge or remove these forks.
Many tools for software engineering, revision control and collaborative authoring use
locking or other concurrency mechanisms to ensure that simple editing histories are always
maintained, and thus to avoid the necessity handling merge and its more complex change
histories. By “simple” editing histories I mean either sequential or tree-structured histories.
While tree structured histories do permit alternative variants of a basic sequence, they are
simple in the sense that any state of the sequence has a single linear, temporally organized
line of descent. Most tools encourage histories of this form, and for them the merge problem
is an exceptional case, only invoked when the normal synchronization mechanisms of the
system are subverted or deliberately suspended.
In traditional version systems, there is no system-enforced inherent relationship between
the contents of one version in the version graph and the contents of its predecessor(s). The
actual relationship of versions in the graph is determined by the users performing check-in
Existing versions are edited by a user, and the results are added to the version graph by a
user operation. Versions are almost always stored in a single logical repository, although it
may be physically distributed across multiple machines. Access control is provided so that
only versions without successors can be updated, adding new nodes to the graph, and to
prevent users from inadvertently creating unwanted versions. When non-tree structured ver-
sion graphs are supported, they are created by user-executed mergeoperations. A merge op-
eration creates a new state that is a descendent of more than one node in the version graph.
The structure of change histories is the other factor in determining how changes interact,
and how conflicts arise and are resolved. Table1.1 (in Section1.4) lists the usual user-visible
history structures in terms of the topology of version graphs. Any general infrastructure
should be able to support these models. One key characteristic of the notions of serializabil-
ity that we are replacing is that changes are temporally ordered in a linear way. When diver-
gent editing occurs, a fork in the history also occurs, and one concern is whether and how to
merge or remove these forks.
Many tools for software engineering, revision control and collaborative authoring use
locking or other concurrency mechanisms to ensure that simple editing histories are always
maintained, and thus to avoid the necessity handling merge and its more complex change
histories. By “simple” editing histories I mean either sequential or tree-structured histories.
While tree structured histories do permit alternative variants of a basic sequence, they are
simple in the sense that any state of the sequence has a single linear, temporally organized
line of descent. Most tools encourage histories of this form, and for them the merge problem
is an exceptional case, only invoked when the normal synchronization mechanisms of the
system are subverted or deliberately suspended.
In traditional version systems, there is no system-enforced inherent relationship between
the contents of one version in the version graph and the contents of its predecessor(s). The
actual relationship of versions in the graph is determined by the users performing check-in
