Chapter 1: Introduction and Overview
The use of computer tools to support the collaborative creation of documents dates from
the first applications of computers to document preparation. Douglas Engelbart’s NLS system
(Engelbart 1984; Engelbart and English 1968; Engelbart, Watson et al. 1973) invented the
major paradigms for user capabilities and interaction styles, including joint-editing facilities
for real-time collaboration, as well as simple archive-based version control, electronic mail
(of drafts and links to drafts), hypertext linkage, structured documents and offline collabo-
ration mechanisms such as commenting facilities. After the ambitious beginnings of the
early systems, work slowed, only to pick up at an accelerating rate in the 80’s and 90’s.
1.1 Overview of this dissertation
This dissertation describes Palimpsest, a new approach to designing collaborative data
sharing toolkits, based on change-oriented concurrency control. This chapter presents a brief
overview of the context of this large area of research, desiderata for collaborative editing
systems, and a detailed discussion of some core problems for collaborative system design: the
problems of concurrency control, consistency, and editing synchronization. Chapter 2 pre-
sents an overview of other approaches to change-oriented concurrency control, and some of
their differences from the Palimpsest approach. Chapter 3 considers the problems of repre-
senting changes to sequences and conflict resolution strategies and prepares the way for
Chapter 4, which presents a formal model of Palimpsest semantics, and proves some impor-
tant basic properties of the model. Chapter 5 considers the issues involved in applying the
formal model to the description of the user facilities and capabilities discussed earlier.
Chapter 6 considers the algorithmic questions in implementing a Palimpsest data store, and
discusses data structures and algorithms for manage one efficiently. Chapter 7 briefly
sketches some of the architectural and systems capabilities that the Palimpsest model sup-
The use of computer tools to support the collaborative creation of documents dates from
the first applications of computers to document preparation. Douglas Engelbart’s NLS system
(Engelbart 1984; Engelbart and English 1968; Engelbart, Watson et al. 1973) invented the
major paradigms for user capabilities and interaction styles, including joint-editing facilities
for real-time collaboration, as well as simple archive-based version control, electronic mail
(of drafts and links to drafts), hypertext linkage, structured documents and offline collabo-
ration mechanisms such as commenting facilities. After the ambitious beginnings of the
early systems, work slowed, only to pick up at an accelerating rate in the 80’s and 90’s.
1.1 Overview of this dissertation
This dissertation describes Palimpsest, a new approach to designing collaborative data
sharing toolkits, based on change-oriented concurrency control. This chapter presents a brief
overview of the context of this large area of research, desiderata for collaborative editing
systems, and a detailed discussion of some core problems for collaborative system design: the
problems of concurrency control, consistency, and editing synchronization. Chapter 2 pre-
sents an overview of other approaches to change-oriented concurrency control, and some of
their differences from the Palimpsest approach. Chapter 3 considers the problems of repre-
senting changes to sequences and conflict resolution strategies and prepares the way for
Chapter 4, which presents a formal model of Palimpsest semantics, and proves some impor-
tant basic properties of the model. Chapter 5 considers the issues involved in applying the
formal model to the description of the user facilities and capabilities discussed earlier.
Chapter 6 considers the algorithmic questions in implementing a Palimpsest data store, and
discusses data structures and algorithms for manage one efficiently. Chapter 7 briefly
sketches some of the architectural and systems capabilities that the Palimpsest model sup-
