vi
PALIMPSEST: A CHANGE-ORIENTED CONCURRENCY
MODEL FOR THE SUPPORT OF COLLABORATIVE APPLICATIONS
(Order No. )
DAVID G. DURAND
Boston University Graduate School of Arts and Sciences, 1999
Major Professor: Wayne Snyder, Professor of Computer Science
ABSTRACT
This dissertation examines the problem of concurrency control in collaborative editing,
both synchronous and asynchronous. It identifies a set of requirements for support of col-
laborative undo, offline operation, and merging of variants. The requirements address the
need to support divergent states while editing, and to support opportunistic collaboration
strategies. Change orientation is identified as key strategy to address these problems.
I formally define a new, change-oriented model for collaborative updating of sequences,
particularly suited the problem of collaborative text editing. The model, Palimpsest, ad-
dresses document locations in terms of the operations that affect them. A new distinction is
introduced between dynamic editing operations, which chare structure between different
versions of a document, and static operations which accurately represent state changes, but
are not updated when other operations are undone. Palimpsest provides a model of the ef-
fects of non-sequential undo and merge for the dynamic operations sequence operations
moveandcopy. These operations have not been supported in previous models of concurrent
update.
Unlike similar change-oriented approaches like operational transformation, Palimpsest
does not depend on synchronization properties of the underlying communication channel,
and knowledge of the states of other instances of the collaborating application. The inde-
pendence of operation representations from application state has architectural implications
for systems based on the model, including the ability to easily support the flexible transition
PALIMPSEST: A CHANGE-ORIENTED CONCURRENCY
MODEL FOR THE SUPPORT OF COLLABORATIVE APPLICATIONS
(Order No. )
DAVID G. DURAND
Boston University Graduate School of Arts and Sciences, 1999
Major Professor: Wayne Snyder, Professor of Computer Science
ABSTRACT
This dissertation examines the problem of concurrency control in collaborative editing,
both synchronous and asynchronous. It identifies a set of requirements for support of col-
laborative undo, offline operation, and merging of variants. The requirements address the
need to support divergent states while editing, and to support opportunistic collaboration
strategies. Change orientation is identified as key strategy to address these problems.
I formally define a new, change-oriented model for collaborative updating of sequences,
particularly suited the problem of collaborative text editing. The model, Palimpsest, ad-
dresses document locations in terms of the operations that affect them. A new distinction is
introduced between dynamic editing operations, which chare structure between different
versions of a document, and static operations which accurately represent state changes, but
are not updated when other operations are undone. Palimpsest provides a model of the ef-
fects of non-sequential undo and merge for the dynamic operations sequence operations
moveandcopy. These operations have not been supported in previous models of concurrent
update.
Unlike similar change-oriented approaches like operational transformation, Palimpsest
does not depend on synchronization properties of the underlying communication channel,
and knowledge of the states of other instances of the collaborating application. The inde-
pendence of operation representations from application state has architectural implications
for systems based on the model, including the ability to easily support the flexible transition
