<chapter id="chapter.entities">
<title/Entities and Protocols - a Background/

<p>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.

<p>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.

<p>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.

<section <TITLE/Distribution of References/

<p>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.

<P>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:

<para class=apropos><TITLE/Replicated/</para>

<p>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.

<para class=apropos><TITLE/Replicated Uniquely/</para>

<p>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. 
 
<para class=apropos><TITLE/Access Structure /</para>

<p> 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
<PTR to=figure.proxy_manager>). 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 id=figure.proxy_manager>
<caption/A Proxy at site A refers to its Manager at site B/
<picture.choice display>
      <picture.extern to="proxy_manager.gif" type=gif>
</picture.choice>
</figure>

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

<para class=apropos><TITLE/Lazy Replication / </para>

<p>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.

<para class=apropos><TITLE/Resource Placeholder / </para>

<p>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.

<section><title/Consistency Protocols/

<p>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. 

<p>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:

<para class=apropos><title/Stationary State/

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

<para class=apropos><title/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.

<para class=apropos><title/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.

<section><title/Distribution of Mozart Entities/

<p><Ptr to ="data-types-dist"> shows the class of reference
distribution and the consistency protocol used for entities in
Mozart.

    <Figure class=table id="data-types-dist">
     <TABLE>
    <TR><TH>Entity Type   <TH>Reference Distribution <TH>Consistency Protocol
    <TR><TD>Port       	  <TD>Access Structure    <TD>Stationary
    <TR><TD>Variable   	  <TD>Access Structure    <TD>Single assignment
    <TR><TD>Cell       	  <TD>Access Structure    <TD>Mobile state
    <TR><TD>Lock       	  <TD>Access Structure    <TD>Mobile state
    <TR><TD>Object     	  <TD>Lazy Replication    <TD>Mobile state
    <TR><TD>Record     	  <TD>Replicated          <TD>none needed
    <TR><TD>Atoms      	  <TD>Replicated    <TD>none needed
    <TR><TD>List       	  <TD>Replicated    <TD>none needed
    <TR><TD>Chunk      	  <TD>Replicated Unique   <TD>none needed
    <TR><TD>Name       	  <TD>Replicated Unique         <TD>none needed
    <TR><TD>Class      	  <TD>Replicated Unique   <TD>none needed
    <TR><TD>Functor    	  <TD>Replicated Unique         <TD>none needed
    <TR><TD>Procedure  	  <TD>Replicated Unique         <TD>none needed
    <TR><TD>Code          <TD>Replicated Unique   <TD>none needed
    <TR><TD>Dictionary 	  <TD>Resource Placeholder    <TD>none needed
    <TR><TD>Array      	  <TD>Resource Placeholder    <TD>none needed
    <TR><TD>Sited Entities<TD>Resource Placeholder   <TD>none needed
    <TR><TD>Builtin    	  <TD>Resource Placeholder    <TD>none needed
    <TR><TD>Constraint Variable   	  <TD>Resource Placeholder    <TD>none needed
  </TABLE>

<section>
<title/  Distributed Memory Management/

<p>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.

<p>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 Counting<note foot>Presented
independently by D I Bevan in <em>Distributed Garbage Collection Using
Reference Counting</em>,1987, and Watson and Watson in <em>An Efficient
Garbage Collection Scheme for Parallel Computer Architecture</em>,
1987.</note> 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.

