Palimpsest: Change-Oriented Concurrency Control For The Support Of Collaborative Applications

This dissertation examines the problem of concurrency control in collaborative editing, both synchronous and asynchronous. Change orientation is identified as a key strategy to address undo, offline operation, and merging of variants. This book defines 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.