58
ordering will not necessarily be based on a total temporal ordering as available to sys-
tems that are not change-complete.
This structural taxonomy of potential zones of conflict will allow focused consideration of
interacting operations without having to examine each possible structural combination indi-
vidually, for each possible pair of operations. This is important because there are a large
number of possible pairwise interactions among even a small set of operations. Fortunately,
we need not exhaustively examine all possible cases.
3.2 The Palimpsest set of basic sequence operations
This section describes the basic operations chosen for Palimpsest. I will describe them and
briefly review some of the implications of their definition as dynamicoperations. In Section
3.3 I will examine the conflicts that can occur with this operation set, and develop some in-
tuition as to what kinds of solutions are most desirable. In Section 3.4, I consider the ques-
tion of how a persistent addressing mechanism can simplify the representation and resolu-
tion of conflicts between dynamic operations. When describing Palimpsest operations I will
depend on the ability to designate ranges within a sequence by means of start and end
points, and to determine whether a point is inside or outside of such a range. Since the op-
erations in question in fact permute sequence elements, and change the order of items, the
assumption that this is possible is, strictly speaking, unwarranted. Section 3.4 will redeem
this assumption by showing how to use the insights developed in considering operational
conflict resolution to define an appropriate meaning for such an ordering.
Palimpsest sequences support 4 primitive operations:
• Insert.This takes a position in a sequence and adds items to that sequence at that loca-
tion. A position is a gap between two items of a sequence.
ordering will not necessarily be based on a total temporal ordering as available to sys-
tems that are not change-complete.
This structural taxonomy of potential zones of conflict will allow focused consideration of
interacting operations without having to examine each possible structural combination indi-
vidually, for each possible pair of operations. This is important because there are a large
number of possible pairwise interactions among even a small set of operations. Fortunately,
we need not exhaustively examine all possible cases.
3.2 The Palimpsest set of basic sequence operations
This section describes the basic operations chosen for Palimpsest. I will describe them and
briefly review some of the implications of their definition as dynamicoperations. In Section
3.3 I will examine the conflicts that can occur with this operation set, and develop some in-
tuition as to what kinds of solutions are most desirable. In Section 3.4, I consider the ques-
tion of how a persistent addressing mechanism can simplify the representation and resolu-
tion of conflicts between dynamic operations. When describing Palimpsest operations I will
depend on the ability to designate ranges within a sequence by means of start and end
points, and to determine whether a point is inside or outside of such a range. Since the op-
erations in question in fact permute sequence elements, and change the order of items, the
assumption that this is possible is, strictly speaking, unwarranted. Section 3.4 will redeem
this assumption by showing how to use the insights developed in considering operational
conflict resolution to define an appropriate meaning for such an ordering.
Palimpsest sequences support 4 primitive operations:
• Insert.This takes a position in a sequence and adds items to that sequence at that loca-
tion. A position is a gap between two items of a sequence.
