Interconnected replicated objects

All local objects that are (transitively) referenced from a transparent replicated object belong to its replicated state. The replicated object (an instance of a replicated class) is therefore called the root object of the replicated graph that consists of all objects reachable from the root object through local references. All objects belonging to the replicated state of a root object are updated, when their root object is updated (at the end of code regions that are synchronized on the root object).

Problems arise, if the system cannot unambiguously determine to which replicated root object some object belongs. This happens, if a single local object is referenced from two or more replicated graphs. If this is the case, the programmer must resolve the situation by implementing a special interface in classes whose instances may serve as interconnection point of replicated graphs. This helps the system to determine the border of replicated graphs correctly.

The following paragraphs further introduce the problem and show a proper solution.

Replicated state

An example of the extent of the replicated state of a replicated object is shown in Figure 1. The replicated object p1 tranistively references objects a, v, s, and e1-e5. All these objects belong to the replicated state of p1 and are kept consistent along with p1.

Figure 1. Single replicated object.

Corresponding objects

Each object that is part of a replicated graph has a corresponding object in each replica (unless PartialReplication is used). If such an object is modified locally on some replica, all its corresponding objects are updated during the next update of the root object.

Figure 2 shows the replicated graph of Figure 1 assuming that there are two replicas of the graph (at rank0 and rank1). Corresponding objects are connected through dashed lines. These connections are pure virtual, since each end of the correspondence is a regular local object in another virtual machine.

Figure 2. Replicated object from Figure 1 replicated on two machines.

Multiple root objects

As long as there is only a single root object per virtual machine, everything is fine. For each object that is part of a replicated graph, it is clear to which graph it belongs. Creating multiple replicated root objects is still not a problem, as long as their replicated graphs are not connected.

If one creates mutliple replicated objects per virtual machine that have common objects in their replicated graph, things start to get complicated. An example of such a situation is shown in Figure 3. The second root object p2 (transitively) references objects v, s1-s3 and e1-e5. Since objects e1-e5 are also referenced from root object p1, it is not obvious to which replicated graph they belong.

Figure 3. Second replicated object that has some of its substates common with the first replicated object.

When replicas of the two replicated graphs in Figure 3 are created, a problematic situation arises. As shown in Figure 4, the objects e1-e5 that are part of the replicated state of p1 and p2 become "schizophrenic" on rank1. The reason is that during replication of p1, a copy of e1-e5 is created on rank1. The same happens during replication of p2. Since e1-e5 are regular Java objects, there is no way for the system to know that they already belong to the replicated graph of p1 (and a copy is already allocated on rank1). Instead, fresh copies e1'-e5' are created on rank1. The correspondence relation is asymmetric as indicated through the dashed lines in Figure 4. E.g., e1 on rank0 corresponds to e1 on rank1 in the context of p1, but to e1' on rank1 in the context of p2.

Figure 4. Problematic situation that occurs, if the replicated objects from Figure 3 are replicated on two machines.


Obviously, there must be a way to decide for objects e1-e5 that they belong to a certain replicated graph. This possibility is provided by the interface uka.patch.PatchableRoot:

public interface PatchableRoot {
    public Object getOwner();

By implementing this interface in the classes of e1-e5, these objects can indicate e.g. that p1 is their owner object by returning p1 from the implemented getOwner() method. The situation with clarified owners is shown in Figure 5.

Figure 5. Solution of the problem in Figure 4 using custom root objects.

When replicating the graphs now, everything works as expected. For each object, only a single copy with proper correspondences will be created per rank. The picture equivalent to the situation shown in Figure 4 would show an exact mirror of the the graph in Figure 5 on rank1.

As a consequence of the propper assignment of objects e1-e5 to root object p1, these objects will only be updated, if p1 is updated. An update to p2 will only affect objects p2, v, and s1-s3.

Last modified 14 years ago Last modified on Mar 23, 2006 1:25:43 AM