84
one address—each one corresponding to a location to which that data was copied or moved.
Deletions are not explicitly mentioned here, because their IDs never appear in addresses.
In working with addresses the function Ids proves useful. For an address p = (I
1 …I
n-1 , i)
we have the following:
Ids(p) = {I
j | 1 < j < n}.
4.2.3 Consistent change sets and causal ordering
The set of legal addresses in a Palimpsest sequence and the total order they take in the
resulting sequence are defined by a set of changes. However, not every set of changes will
produce a well-ordered set of addresses. A set of changes must satisfy certain minimal condi-
tions, which turn out to have a natural relationship to the notion of causal orderingof
changes. The usual notion of causal ordering was first defined in (Lamport 1978), in the con-
text of destructive database updates. Lamport’s causal ordering was a partial order on opera-
tions, in which an operation preceded another operation if it occurred earlier and affected
the same location. Lamport’s ordering relaxed the constraints of total temporal ordering by
recognizing that non-interfering operations need not be ordered with respect to each other.
Palimpsest needs a similar notion (a partial order on operations, derived from but more
relaxed than a temporal order). While Palimpsest does not have the same kinds of conflicts
between changes, it does have addressing dependencies between changes. In a system, Pal-
impsest changes will be created every time that a user performs a new operation, and those
changes must reference Palimpsest addresses. Some (like move, copy, and insert) will create
new addresses. However, there are significant restrictions on the relations of these changes
to the addresses they use, because the changes must be created in some temporal order, and
because each address is constructed from the IDs of previously constructed changes.The criti-
cal observation is that the addresses referenced by a change should already exist at the time
that change is created.
one address—each one corresponding to a location to which that data was copied or moved.
Deletions are not explicitly mentioned here, because their IDs never appear in addresses.
In working with addresses the function Ids proves useful. For an address p = (I
1 …I
n-1 , i)
we have the following:
Ids(p) = {I
j | 1 < j < n}.
4.2.3 Consistent change sets and causal ordering
The set of legal addresses in a Palimpsest sequence and the total order they take in the
resulting sequence are defined by a set of changes. However, not every set of changes will
produce a well-ordered set of addresses. A set of changes must satisfy certain minimal condi-
tions, which turn out to have a natural relationship to the notion of causal orderingof
changes. The usual notion of causal ordering was first defined in (Lamport 1978), in the con-
text of destructive database updates. Lamport’s causal ordering was a partial order on opera-
tions, in which an operation preceded another operation if it occurred earlier and affected
the same location. Lamport’s ordering relaxed the constraints of total temporal ordering by
recognizing that non-interfering operations need not be ordered with respect to each other.
Palimpsest needs a similar notion (a partial order on operations, derived from but more
relaxed than a temporal order). While Palimpsest does not have the same kinds of conflicts
between changes, it does have addressing dependencies between changes. In a system, Pal-
impsest changes will be created every time that a user performs a new operation, and those
changes must reference Palimpsest addresses. Some (like move, copy, and insert) will create
new addresses. However, there are significant restrictions on the relations of these changes
to the addresses they use, because the changes must be created in some temporal order, and
because each address is constructed from the IDs of previously constructed changes.The criti-
cal observation is that the addresses referenced by a change should already exist at the time
that change is created.
