74
3.4.3 The structure of Palimpsest addresses
The addresses we will use are based on the assignment of unique identifiers to each
change. Each change has a globally unique identifier. Every element of a sequence is given
an identifier consisting of the name of the insertion that originally inserted it, augmented
with its position in the subsequence created by that insertion change. When a move or copy
operation creates a new subsequence at a different point, new addresses are created, pre-
fixed with the identifier of the move or copy operation. These new addresses retain the same
relative order with respect to each other as their original, non-prefixed forms do. With re-
spect to all other addresses, they are ordered as the destination of the move or copy opera-
tion.
This address format is quite simple, and ensures that addresses are invariant, as, rather
than being based on changing offsets with respect to some particular state of the sequence,
they depend only on the identifiers of changes, which are invariant. This turns out to be a
useful property when implementing distributed systems, since the addresses needed to rep-
resent an operation do not need to be transformed in order to execute that operation. The
invariance of the addresses and the operations represented with them are invariant.
While uniqueness of identifiers can be hard to ensure, methods for creating unique Ids
are relatively well known (Coulouris and Dollimore 1988). Cryptographic hash codes like MD5
(Rivest 1992) also allow independent assignment of unique identifiers based on the contents
of a data object itself. The most basic form of address in the system will the change ID of an
insertion change, plus the offset of an insertion point within the data inserted by that
change. The initial state of a document is defined by an initial insertion operation, which
unlike all the other insertions in a document, does not have an address identifying the in-
sertion point.
3.4.3 The structure of Palimpsest addresses
The addresses we will use are based on the assignment of unique identifiers to each
change. Each change has a globally unique identifier. Every element of a sequence is given
an identifier consisting of the name of the insertion that originally inserted it, augmented
with its position in the subsequence created by that insertion change. When a move or copy
operation creates a new subsequence at a different point, new addresses are created, pre-
fixed with the identifier of the move or copy operation. These new addresses retain the same
relative order with respect to each other as their original, non-prefixed forms do. With re-
spect to all other addresses, they are ordered as the destination of the move or copy opera-
tion.
This address format is quite simple, and ensures that addresses are invariant, as, rather
than being based on changing offsets with respect to some particular state of the sequence,
they depend only on the identifiers of changes, which are invariant. This turns out to be a
useful property when implementing distributed systems, since the addresses needed to rep-
resent an operation do not need to be transformed in order to execute that operation. The
invariance of the addresses and the operations represented with them are invariant.
While uniqueness of identifiers can be hard to ensure, methods for creating unique Ids
are relatively well known (Coulouris and Dollimore 1988). Cryptographic hash codes like MD5
(Rivest 1992) also allow independent assignment of unique identifiers based on the contents
of a data object itself. The most basic form of address in the system will the change ID of an
insertion change, plus the offset of an insertion point within the data inserted by that
change. The initial state of a document is defined by an initial insertion operation, which
unlike all the other insertions in a document, does not have an address identifying the in-
sertion point.
