Chapter 3: Operations and Conflicts in Sequences
This chapter examines Palimpsest’s abstract data structure, the sequence, presents the set
of operations that I have formalized and implemented in Palimpsest, and examines the key
issues of operation interaction that arise when applying change-based concurrency control.
In the examples in this chapter, I present sequences from the point of view of text editors.
For text editing, sequences are fundamental, suitable for modeling a word processing docu-
ment or other text file, whether treated as a sequence of lines, of characters, of characters
and formatting codes or hierarchically nested (themselves sequential) containers. Other rep-
resentations may augment, but they do not change text’s fundamentally sequential nature.
4
I will use arguments about desirable text editor behavior and implementation tradeoffs
when choosing default policies, and when forced to choose between incompatible options for
the data structure model. This is less application-specific than it may seem because the im-
plementation of text editors makes extremely complex demands on a sequence implementa-
tion, both in terms of the operations permitted and in terms of the level of interactive per-
formance required. A decent text editor requires a superset of the sequence operations
demanded by most applications. The purpose of this chapter is to examine sequence editing
4
One of the goals of this work is to enable sophisticated hypertext functionality, like fine-grained
anchor tracking. Given that, the comments about the “sequential nature of text” may seem to violate
the expectations of hypertext systems, devoted as they are to enabling non-sequential presentation
and navigation of data. The answer to this contradiction is that the non-sequential nature of hyper-
text is at a macrolevel, while the fundamental sequentiality of text occurs at the micro-level of words
and letters. Anagrams may be amusing, but they are not a way to enhance understanding! Underlying
any kind of hypertext system must be some sequence management to handle the words of the hyper-
document itself.
This chapter examines Palimpsest’s abstract data structure, the sequence, presents the set
of operations that I have formalized and implemented in Palimpsest, and examines the key
issues of operation interaction that arise when applying change-based concurrency control.
In the examples in this chapter, I present sequences from the point of view of text editors.
For text editing, sequences are fundamental, suitable for modeling a word processing docu-
ment or other text file, whether treated as a sequence of lines, of characters, of characters
and formatting codes or hierarchically nested (themselves sequential) containers. Other rep-
resentations may augment, but they do not change text’s fundamentally sequential nature.
4
I will use arguments about desirable text editor behavior and implementation tradeoffs
when choosing default policies, and when forced to choose between incompatible options for
the data structure model. This is less application-specific than it may seem because the im-
plementation of text editors makes extremely complex demands on a sequence implementa-
tion, both in terms of the operations permitted and in terms of the level of interactive per-
formance required. A decent text editor requires a superset of the sequence operations
demanded by most applications. The purpose of this chapter is to examine sequence editing
4
One of the goals of this work is to enable sophisticated hypertext functionality, like fine-grained
anchor tracking. Given that, the comments about the “sequential nature of text” may seem to violate
the expectations of hypertext systems, devoted as they are to enabling non-sequential presentation
and navigation of data. The answer to this contradiction is that the non-sequential nature of hyper-
text is at a macrolevel, while the fundamental sequentiality of text occurs at the micro-level of words
and letters. Anagrams may be amusing, but they are not a way to enhance understanding! Underlying
any kind of hypertext system must be some sequence management to handle the words of the hyper-
document itself.
