Palimpsest: Change-oriented Concurrency Control for Collaborative Applications


David G. Durand

Available PDF Downloads

Download Entire Dissertation
(pages 1-140)
Entire Dissertation (pages 1-140)

Palimpsest: Change-oriented Concurrency Control for Collaborative Applications

This dissertation examines the problem of concurrency control in collaborative editing, both synchronous and asynchronous. It identifies a set of requirements for support of collaborative 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 a key strategy to address these problems.

I formally define a new, change-oriented model for collaborative updating of sequences, particularly suited to the problem of collaborative text editing. The model, Palimpsest, addresses document locations in terms of the operations that affect them. A new distinction is introduced between dynamic editing operations, which share 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 effects of non-sequential undo and merge for the dynamic operations sequence operations move and copy. 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 independence of operation representations from application state has architectural implications for systems based on the model, including the ability to easily support the flexible transition between synchronous and asynchronous editing. It imposes minimal consistency and synchronization requirements on the underlying transport channel, supports recovery when communication occurs over lossy channels, and imposes minimal synchronization demands on the human users of a collaborative application.

Table of Contents

Palimpsest: Change-oriented Concurrency Control for Collaborative Applications

Author(s): David G. Durand
Keyword(s): cs; cscw; collaboration; editing; dissertation

Search Results

No results found