40
applications manipulate editing histories, as in Timewarp (Edwards 1997; Edwards and Mynat
1997), usually adding new editing operations to a particular history (and thus updating the
history), sometimes removing changes from that history (and undoing previously done op-
erations, or otherwise adjusting or examining its structure (revealing the actions that have
affected it, and merging divergent states). Although histories may have different forms, each
history definesa state of the data structure. Data is shared by sharing histories, and
concurrency is controlled by managing the differences between histories (as determined by
the changes that belong to them).
I will concentrate on the logical and formal problems involved in implementing systems
that treat changes as first-class objects. In presenting this kind of capability, Timewarp ap-
peals to the notion of time travel and quantum uncertainty as a guide to the concurrency
model and its user interface. Palimpsest instead appeals to the Copenhagen, or “multiple
worlds” interpretation of quantum mechanics. Histories exist only as they are explicitly con-
structed by an application, and many alternate histories are possible, given a set of opera-
tions that apply to the same data. Applications may choose to construct linear, single state,
branching or generalized acyclic histories. Any set of changes defines a host of possible al-
ternative states of the shared data, depending on exactly how the changes are combined and
limited only by logical constraints as to what combinations are meaningful. Only states that
“come to consciousness” by being instantiated by an application are actually realized, even
temporarily. The many never-instantiated states are important, however. Like a halo of vir-
tual particles, they represent authorial options for revisions never made. The size of this vir-
tual state space essentially determines the flexibility of a change-oriented concurrency sys-
tem, since it is exactly this set of potential states that determines what options for resolving
conflicts are available, each legal choice represents a possibility that might be useful in some
situation.
applications manipulate editing histories, as in Timewarp (Edwards 1997; Edwards and Mynat
1997), usually adding new editing operations to a particular history (and thus updating the
history), sometimes removing changes from that history (and undoing previously done op-
erations, or otherwise adjusting or examining its structure (revealing the actions that have
affected it, and merging divergent states). Although histories may have different forms, each
history definesa state of the data structure. Data is shared by sharing histories, and
concurrency is controlled by managing the differences between histories (as determined by
the changes that belong to them).
I will concentrate on the logical and formal problems involved in implementing systems
that treat changes as first-class objects. In presenting this kind of capability, Timewarp ap-
peals to the notion of time travel and quantum uncertainty as a guide to the concurrency
model and its user interface. Palimpsest instead appeals to the Copenhagen, or “multiple
worlds” interpretation of quantum mechanics. Histories exist only as they are explicitly con-
structed by an application, and many alternate histories are possible, given a set of opera-
tions that apply to the same data. Applications may choose to construct linear, single state,
branching or generalized acyclic histories. Any set of changes defines a host of possible al-
ternative states of the shared data, depending on exactly how the changes are combined and
limited only by logical constraints as to what combinations are meaningful. Only states that
“come to consciousness” by being instantiated by an application are actually realized, even
temporarily. The many never-instantiated states are important, however. Like a halo of vir-
tual particles, they represent authorial options for revisions never made. The size of this vir-
tual state space essentially determines the flexibility of a change-oriented concurrency sys-
tem, since it is exactly this set of potential states that determines what options for resolving
conflicts are available, each legal choice represents a possibility that might be useful in some
situation.
