41
The Palimpsest formal model precisely describes a particular set of fundamental sequence
operations and merge strategies. This formal model is one solution drawn from a complex
design space; it is based on both practical considerations and logical constraints. Because of
the many interactions of the basic data model with user interface, systems infrastructure
and user expectations, the application problem (even for one application) almost certainly
has no singleanalytically determined solution; it rather allows only varying compromises
among conflicting requirements. While Palimpsest application programmers can be (and are)
offered some choice in terms of strategies for operation conflict resolution, a data-oriented,
declarative approach requires a clearly defined base level semantics (which may not be to-
tally independent of policy) and which forms the foundation on which a particular system
can be built.
2.2 Data types and operation types
If operations are to be the fundamental entities in controlling concurrent access and ed-
iting of a data structure, two factors are of primary importance. The exact data structure
being shared is one critical factor. Another is the interaction of changes when they are com-
bined into histories. Finally, the structure of histories affects the definitions of operations
and their precise interactions. While these factors are conceptually independent, specific
decisions on any of these dimensions interact with the possible decisions on other dimen-
sions. Furthermore, even for the extendable sequence, the data type for which I will consider
a relatively full range of possibilities, the appropriateness of particular history structures and
interactions may vary depending on the specific application, because of differing, equally
sensible, possible methods of resolving conflicts. Palimpsest makes as few policy decisions as
possible, while ensuring that textual authoring is accommodated by the resulting system.
Perhaps the primary factor in determining the set of operations for a data structure is the
data structure itself. I will consider data structures as algebraic data types in the style of a
The Palimpsest formal model precisely describes a particular set of fundamental sequence
operations and merge strategies. This formal model is one solution drawn from a complex
design space; it is based on both practical considerations and logical constraints. Because of
the many interactions of the basic data model with user interface, systems infrastructure
and user expectations, the application problem (even for one application) almost certainly
has no singleanalytically determined solution; it rather allows only varying compromises
among conflicting requirements. While Palimpsest application programmers can be (and are)
offered some choice in terms of strategies for operation conflict resolution, a data-oriented,
declarative approach requires a clearly defined base level semantics (which may not be to-
tally independent of policy) and which forms the foundation on which a particular system
can be built.
2.2 Data types and operation types
If operations are to be the fundamental entities in controlling concurrent access and ed-
iting of a data structure, two factors are of primary importance. The exact data structure
being shared is one critical factor. Another is the interaction of changes when they are com-
bined into histories. Finally, the structure of histories affects the definitions of operations
and their precise interactions. While these factors are conceptually independent, specific
decisions on any of these dimensions interact with the possible decisions on other dimen-
sions. Furthermore, even for the extendable sequence, the data type for which I will consider
a relatively full range of possibilities, the appropriateness of particular history structures and
interactions may vary depending on the specific application, because of differing, equally
sensible, possible methods of resolving conflicts. Palimpsest makes as few policy decisions as
possible, while ensuring that textual authoring is accommodated by the resulting system.
Perhaps the primary factor in determining the set of operations for a data structure is the
data structure itself. I will consider data structures as algebraic data types in the style of a
