# 3 Entities and Protocols - a Background

Distribution in Mozart is realized by sharing language entities. How this is done depends on if they are stateless or stateful. Stateless entities are replicated between sites whereas stateful entities create access structures. The local semantics of the stateful entities are maintained in a distributed setting by a number of consistency protocols.

Mozart entities may be in one of two states: plain or globalized. A plain entity is only referenced within its virtual machine. This virtual machine is called the entity's home site. A plain entity will become globalized at the instance when a reference to it is shared. A globalized entity is returned to being plain when no more remote references exist; this is called localization.

The Distribution Subsystem offers four kinds of distribution behavior and four kinds of replication patterns. Distribution behavior and replication patterns are paired together to create different distribution semantics. Each entity type in Mozart has been assigned a pair to define its distributed semantics and behavior.

## 3.1 Distribution of References

At globalization an entity is given a globally unique identity (GUId). This name is used to identify imported references, to see if a copy of the entity already exists at the importing site. The GUId consists of a reference to the home site and an identifier that is unique at the home site.

When entities are transferred from one site to another five kinds of replication patterns exist. The importing site is responsible for building a structure according to the replication pattern. The five patterns are described here:

Replicated

Replicated entities do not have a GUId. Instead enough information is transferred at distribution time to enable the importer to build a complete copy of the data structure. Without a GUId it is not possible to determine whether the entity already exists at the importing site or not.

Replicated Uniquely

An entity that is Replicated Uniquely transfers enough information to build a complete replica of it at the importing site. In contrast to Replicated entities, Replicated Uniquely entities have a GUId that enables the importer to make sure that there may exist one and only one instance of the entity at the importing site.

Access Structure

When a stateful entity is globalized, a Manager is constructed at its home site. References to the the entity imported at other sites result in the construction of proxies pointing to the manager (see Figure 3.1). This structure is called an access structure. The GUId of the entity is used to ensure that one and only one proxy is built at site that imports references to the entity.

Figure 3.1: A Proxy at site A refers to its Manager at site B

Access structures are used to maintain reference consistency and as a base for the consistency protocols described below.

Lazy Replication

Lazy Replication is a special case of Replicated Uniquely. Instead of sending the whole value of the entity the possibility to build an access structure is transferred. If no instance of the entity exists at the importer, the access structure is built. When a Lazy Replicated entity is accessed for the first time the value of the entity is requested and the access structure is removed when the value arrives.

Resource Placeholder

Some data structures should not be available remotely. This is handled by replacing those entities with a placeholder on which no operations can be performed except equality. This placeholder is reflected to language level as a Resource.

## 3.2 Consistency Protocols

As stated earlier, the DS uses consistency protocols to maintain the semantics of a plain entity also when it has been globalized. Note that this is of course not necessary for replicated stateless entities.

Stateful entities can have a real state or be single assignment, where single assignment means transforming into another entity once. This is used to implement distributed logic variables. Single assignment entities can be dealt with efficiently by a proxy-manager structure where the manager knows and notifies its proxies. Other stateful entities may implement distribution by letting their state move around to active proxies or by letting a manager act as a server for read and write requests. This gives us with three different protocols for maintaining entity semantics:

Stationary State

The manager maintains the state of a stateful entity locally, and proxies send read and write requests asynchronously to access the state.

Mobile State

Any proxy can attract the state of a stateful entity and operate on it locally as on a plain entity while the state is present.

Single Assignment

The manager knows all of its proxies and can administer any request to transform the entity to a reference to another entity, and forward this to all proxies.

## 3.3 Distribution of Mozart Entities

Table 3.1 shows the class of reference distribution and the consistency protocol used for entities in Mozart.

Entity Type | Reference Distribution | Consistency Protocol
--- | --- | ---
Port | Access Structure | Stationary
Variable | Access Structure | Single assignment
Cell | Access Structure | Mobile state
Lock | Access Structure | Mobile state
Object | Lazy Replication | Mobile state
Record | Replicated | none needed
Atoms | Replicated | none needed
List | Replicated | none needed
Chunk | Replicated Unique | none needed
Name | Replicated Unique | none needed
Class | Replicated Unique | none needed
Functor | Replicated Unique | none needed
Procedure | Replicated Unique | none needed
Code | Replicated Unique | none needed
Dictionary | Resource Placeholder | none needed
Array | Resource Placeholder | none needed
Sited Entities | Resource Placeholder | none needed
Builtin | Resource Placeholder | none needed
Constraint Variable | Resource Placeholder | none needed

Table 3.1.

## 3.4 Distributed Memory Management

Every Mozart site performs garbage collection locally. During this process all replicated entities and proxies are treated as plain Mozart data structures. Managers on the other hand act as roots for the local garbage collector.

To ensure that globalized entities are localized if and only if no more remote references exist, the DS has a distributed reference consistency algorithm. This is currently implemented by an extended version of Weighted Reference Counting1 called Secondary Weight. Weighted Reference Counting is an algorithm that assigns a total weight to an entity. When references are shared, a part of this weight is shared too. When all weight is present at the manager, the entity is local. The original algorithm has a problem in that weight is limited. Secondary Weight overcomes that problem, by allowing proxies to create a new range of weight that they manage.

1. Presented independently by D I Bevan in Distributed Garbage Collection Using Reference Counting,1987, and Watson and Watson in An Efficient Garbage Collection Scheme for Parallel Computer Architecture, 1987.