151
would leave some changes causally disconnected; such a problem will be detected on receipt
of the change whose destination is missing. A destination collision could occur as the result
of a merge of changes created at disconnected sites, but is also easily detected at the time
that the conflicting change is added to the local change store. All other cases that might be
interpreted as conflicts have Palimpsest-defined resolutions. Detection is a simple matter of
checking new changes for collisions or bad references when they arrive.
Requirement 8 asks for a guarantee of sensible results. This is the lowest priority re-
quirement because it is obviously impossible to meet fully. As anyone who has ever collabo-
rated on a document would agree, some conflicts are not possible even for a human to disen-
tangle. The Palimpsest operations have been carefully designed to interact in the most useful
possible fashion, but no machine-generated answer to concurrency problems will be perfect.
Some tasks remain to the humans engaged in any collaboration.
In conclusion, Palimpsest meets almost all of the goals given in chapter one. Where a
goal is not completely met, Palimpsest provides features that least partially address it. The
model itself is based on a new and thorough analysis of sequence editing and change con-
flicts including the operations move and copy, not previously considered.
8.2 Conclusion
The overall approach of the Palimpsest model is to turn a tricky algorithmic and synchro-
nization problem into a complex, but nonetheless relatively standard data structure problem.
This is accomplished by transforming a temporal problem into an atemporal one. The key is
to represent complete histories in a way that enables alternate histories and their results to
be reliably manipulated and examined. This transformation has several interesting side ef-
fects. It provides immutable representations for operations on potentially very different
states of a shared object, and it provides a global address space that is robust across changes
in the object in question.
would leave some changes causally disconnected; such a problem will be detected on receipt
of the change whose destination is missing. A destination collision could occur as the result
of a merge of changes created at disconnected sites, but is also easily detected at the time
that the conflicting change is added to the local change store. All other cases that might be
interpreted as conflicts have Palimpsest-defined resolutions. Detection is a simple matter of
checking new changes for collisions or bad references when they arrive.
Requirement 8 asks for a guarantee of sensible results. This is the lowest priority re-
quirement because it is obviously impossible to meet fully. As anyone who has ever collabo-
rated on a document would agree, some conflicts are not possible even for a human to disen-
tangle. The Palimpsest operations have been carefully designed to interact in the most useful
possible fashion, but no machine-generated answer to concurrency problems will be perfect.
Some tasks remain to the humans engaged in any collaboration.
In conclusion, Palimpsest meets almost all of the goals given in chapter one. Where a
goal is not completely met, Palimpsest provides features that least partially address it. The
model itself is based on a new and thorough analysis of sequence editing and change con-
flicts including the operations move and copy, not previously considered.
8.2 Conclusion
The overall approach of the Palimpsest model is to turn a tricky algorithmic and synchro-
nization problem into a complex, but nonetheless relatively standard data structure problem.
This is accomplished by transforming a temporal problem into an atemporal one. The key is
to represent complete histories in a way that enables alternate histories and their results to
be reliably manipulated and examined. This transformation has several interesting side ef-
fects. It provides immutable representations for operations on potentially very different
states of a shared object, and it provides a global address space that is robust across changes
in the object in question.
