85
To formalize this notion, define the set refs(I)of all changes directly referenced by a
change cwith IDI.
Definition 4.2:For a changec,such thatId(c) = I,
1. Ifcis an insertion,I[a, s], thenrefs(I) = Ids(a).
2. Ifcis a deletion,D[a
1 , a
2 ], thenrefs(I) = Ids(a
1 ) ¨ Ids(a
2 ).
3. Ifcis a move,M[a
1 , a
2 , d], thenrefs(I) = Ids(a
1 ) ¨ Ids(a
2 ) ¨ Ids(d).
4. Ifcis a copy,C[a
1 , a
2 , d], thenrefs(I) = Ids(a
1 ) ¨ Ids(a
2 ) ¨ Ids(d).
The temporal ordering constraint on change creation means that in an implementation,
each change (with ID I) is created at some timetand that all changes inrefs(I)must have
been created at some earlier time t’. This requirement can be formalized without explicitly
invoking the notion of temporal ordering, by defining a reference relation between changes.
Definition 4.3:Therefersrelation<
r is defined as follows:
1. For any pair of changesc
1 , c
2 , with IDsI
1 , I
2 , c
1 e refs(I
2 ) I
1 <
r I
2
2. Ifa <
r b,andb <
r c,thena <
r c.
The conditions that need to be imposed on a set of changes now correspond to properties
of <
r . The most important type of change set is a causal set.
Definition 4.4:A causal setSis one where<
r is an irreflexive partial order over the IDs
of every change in S, where¨
n (refs(I
n ) e S) is a subset ofS, and whereScontains an inser-
tion whose ID is the minimal element under<
r .
All changes in the set are related to the minimal insertion, directly or indirectly. There
are also no “missing changes” referred to, but not present, nor any changes that refer indi-
rectly to themselves. An implementation can easily ensure these conditions by only creating
changes that refer only to already existing changes. We will refer to the greatest lower
bound of a set Sunder<
r as GLB
r (S). For any causal change set, such a lower bound exists.
Theorem 4.1:The minimal element of a causal set under<
r has destination nil.
To formalize this notion, define the set refs(I)of all changes directly referenced by a
change cwith IDI.
Definition 4.2:For a changec,such thatId(c) = I,
1. Ifcis an insertion,I[a, s], thenrefs(I) = Ids(a).
2. Ifcis a deletion,D[a
1 , a
2 ], thenrefs(I) = Ids(a
1 ) ¨ Ids(a
2 ).
3. Ifcis a move,M[a
1 , a
2 , d], thenrefs(I) = Ids(a
1 ) ¨ Ids(a
2 ) ¨ Ids(d).
4. Ifcis a copy,C[a
1 , a
2 , d], thenrefs(I) = Ids(a
1 ) ¨ Ids(a
2 ) ¨ Ids(d).
The temporal ordering constraint on change creation means that in an implementation,
each change (with ID I) is created at some timetand that all changes inrefs(I)must have
been created at some earlier time t’. This requirement can be formalized without explicitly
invoking the notion of temporal ordering, by defining a reference relation between changes.
Definition 4.3:Therefersrelation<
r is defined as follows:
1. For any pair of changesc
1 , c
2 , with IDsI
1 , I
2 , c
1 e refs(I
2 ) I
1 <
r I
2
2. Ifa <
r b,andb <
r c,thena <
r c.
The conditions that need to be imposed on a set of changes now correspond to properties
of <
r . The most important type of change set is a causal set.
Definition 4.4:A causal setSis one where<
r is an irreflexive partial order over the IDs
of every change in S, where¨
n (refs(I
n ) e S) is a subset ofS, and whereScontains an inser-
tion whose ID is the minimal element under<
r .
All changes in the set are related to the minimal insertion, directly or indirectly. There
are also no “missing changes” referred to, but not present, nor any changes that refer indi-
rectly to themselves. An implementation can easily ensure these conditions by only creating
changes that refer only to already existing changes. We will refer to the greatest lower
bound of a set Sunder<
r as GLB
r (S). For any causal change set, such a lower bound exists.
Theorem 4.1:The minimal element of a causal set under<
r has destination nil.
