The eLinda Project: Overview

The extensions that have been made in the eLinda system provide the programmer with a somewhat higher level of control over the communication mechanisms than is normally the case in Linda systems.  This has been done with a view to improving the performance, and to making the performance issues more explicit (aiding predictability).  These extensions have been made with multimedia applications in mind, but also considering the requirements of other distributed applications.

Usually some form of program source preprocessor is used with Linda systems to translate the Linda operations into the actual forms used by the host language.  Currently a preprocessor is not provided for eLinda and so all interaction with the system takes place using the standard Java function calling and parameter passing mechanisms.  However, the examples given below all make use of a simplified syntax (referred to as the ideal syntax) such as might be supported by a preprocessor.

The Extensions in eLinda

The extensions take three forms.  The first is an additional form of output operation, which provides the programmer with a greater degree of control of the underlying network communication.  The second is a mechanism to allow customised searching algorithms to be integrated into the eLinda system.  Lastly, support for multimedia data types has been added.  Each of these topics will now be discussed in further detail.

Explicit Broadcast Communication

Two types of output operation are now provided to reflect explicitly a choice of optimised internal tuple space implementation strategies.  These are a "point-to-point" mechanism (using non-replicated data) and a "broadcast" mechanism (using replicated data).  This contrasts with the existing Linda mechanism where data is written to tuple space using a single instruction (out), but is then read using one of two methods (in or rd, or the equivalent predicate forms).  In effect, the use of in implies a form of exclusive point-to-point communication, in that one process places a tuple into tuple space and it is then removed by another.  Similarly, the use of rd suggests a form of shared, or broadcast (read-only), communication, as several processes may obtain copies of the tuple.  To allow the programmer to take advantage of this behaviour, a new output operation, wr, has been added in eLinda, which will broadcast the tuple throughout the processor network, whereas out will place a single tuple in tuple space.  These mechanisms provide the programmer with the necessary facilities to express shared, read-only access to data (wr-rd), or exclusive, delete/modify access (out-in).  It should be noted that this usage is not enforced by the system.  For example, it may occasionally be necessary to update data that is otherwise shared in a read-only fashion.  In such a case a tuple would be broadcast using wr, accessed using rd, and then removed for updating using in.  This would result in a performance penalty as all the broadcast tuples would have to be deleted.  Similarly, rd may be used to retrieve a tuple placed in tuple space using out, but a search of all the processors involved in the computation may be required to locate it.

The Programmable Matching Engine

The second extension is to provide a programmable matching engine for the retrieval of tuples, allowing the use of more flexible criteria for the associative addressing of tuples.  For example, in dealing with numeric data one might require a tuple which has a value that is "close to" some specified value (possibly using fuzzy set membership functions).  In a graphical context, where the tuples represent the objects in an image, one might require a tuple corresponding to an object lying within a specified area of the image.  Such queries can usually be expressed using the standard Linda associative matching methods, but will generally be quite inefficient.  For example, the application might have to retrieve all tuples of the required type, select one of interest and then return the rest to tuple space.  When the tuple space is fully distributed, as it is in the eLinda system, searching for a tuple may involve accessing the sections held on all the processors in parallel.  This problem is handled efficiently in eLinda by distributing the matching engine so that network traffic is minimised.  For example, in searching for the "largest" tuple, each section of the tuple space would be searched locally for the largest tuple and that returned to the originating process which would then select the largest of all the replies received.  The syntax currently used to specify the matcher which is to be used is op.matcher, where op is one of the eLinda input operations and matcher specifies the customised matching routine to be used(This is the ideal syntax, not the actual Java code).  In addition, the extended syntax ?= is used to identify which field (or fields) is to be used by the non-standard matching routine.  For example, the command in.maximum("point", ?=x, ?y) specifies an in operation using a matcher which will find the tuple with the maximum x value.  Omitting the matcher specification causes the system to use the "standard" technique of matching for strict equality.

A particularly useful feature of Java for the implementation of the programmable matching engine is the interface mechanism provided by the language.  This allows the system designer to specify the mechanisms which must be provided by the user in order to implement a matching algorithm, without dictating the implementation details.  The interface for the programmable matching engine is shown below.

  public interface ProgrammableMatcher
    { /** This function compares one anti-tuple with a list of tuples.
        * This is needed for all operations, but particularly for
        * non-blocking operations (i.e. rdp and inp).
        */
      public Tuple matchList (AntiTuple a, TupleIterator t)
          throws MatcherException;
      
      /** This function compares one anti-tuple with one tuple.
        * This is needed only for blocking operations (i.e. in and rd)
        * where tuples may come in one at a time (of course, it can also
        * be used by the matchList function).
        * If a matcher is never to be used in a blocking operation this
        * can simply return false.
        */
      public boolean match (AntiTuple a, Tuple t)
          throws MatcherException;
      
    } // interface ProgrammableMatcher

The writer of a matching algorithm may implement it in any class, which may or may not be part of a particular application.  An object of this class must implement the ProgrammableMatcher interface (and thus the two required matching functions described in the code above) and it can then be passed to the eLinda system and be used by it.

Writing such a matcher is not a trivial operation.  Various library calls are provided to allow the matcher to interact directly with the eLinda system (e.g. retrieving tuples from tuple space, replacing unwanted tuples, deleting local and remote tuples, broadcasting requests to other processors and subsequently retrieving the results of such requests, etc.).  However, this interaction allows the programmer to access the tuples in tuple space at a lower level of abstraction than usual, and care needs to be taken to preserve the semantics of Linda tuple retrieval operations.  As an indication of the complexity of writing a customised matching algorithm, a matcher to find the closest numeric value for a particular field (or fields) takes approximately 190 lines of (extensively commented) Java code; a matcher that returns a total of numeric tuple fields is written in 175 lines of code.

The programmable matching engine concept has some aspects in common with the recent adoption of mobile agents[Conde].  Effectively, a customised matcher written for the eLinda programmable matching engine is a form of mobile agent that is distributed on a network to find a matching tuple (or tuples).  This provides the same performance advantage as for mobile agents, namely that the need to move large amounts of data across the network is minimised by doing the processing where the data is to be found rather than centrally.

Support for Multimedia

The third feature of eLinda is its support for multimedia data.  Tuples in eLinda may contain any of the primitive data types supported by Java (int, char, double, float, byte, short, long and boolean) as well as standard Java String objects.  Furthermore, any Java object may be added to a tuple (making use of the polymorphism supported by Java), although this limits the type checking that can be performed by the eLinda system (the only restriction is that the object must be serializable).  In this way the eLinda system attempts to provide the maximum possible functionality for general purpose applications.

To this basic functionality has been added the ability to use a MultiMediaResource object in an eLinda tuple.  This class acts as a wrapper to the underlying Java Media Framework (JMF) multimedia resource.  In particular the implementation of the MultiMediaResource class provides support (transparent to the application programmer) for any necessary buffering of data, fetching or streaming of multimedia data across the network, etc.

As an example, in order to search for and present a multimedia resource something like the following might be written using the eLinda extensions:

  MultiMediaResource m;
  if (inp("Movies", "Star Wars", ?m))
    m.play();
  else
    System.out.println("Star Wars is unavailable");