We describe the use
of Gofer type classes in building an interface to spaces, which highlights
and extends the traditional associative access mechanism. We then show
how processes can be added to Gofer, and how we can combine spaces and
processes to produce a parallel functional language, which we have called
Astro-Gofer.
(Postscript
or Postscript (.gz))
The extension of Linda to include multiple tuple spaces has introduced this new problem as processes are now able to create tuple spaces, spawn other processes into these tuple spaces, and store tuples (data) into these tuple spaces, but are unable to delete any of the objects (tuples, tuple spaces and processes) or even decide about their usefulness.
In this paper we
begin by showing that the main problem in introducing garbage collection
into Linda is the lack of sufficient information about the effectiveness
of Linda objects. We then describe techniques for maintaining a structure
to be used by a garbage collection algorithm of tuple spaces.
(Postscript
or Postscript (.gz))
Linda is a parallel and distributed coordination language, which supports generative communication via interaction with tuples in tuple spaces, which is an ideal representation for cases and case bases, respectively.
The CBR retrieval
operations identified herein have been implemented in Linda, and have displayed
the suitability of Linda for implementing distributed CBR systems, and
the great potential for parallelisation. The retrieval operations have
been generalised to generic operations (algorithmic skeletons) for Linda:
mapping and closure operations, and constraint versions of the existing
primitives.
This paper describes
an open Linda-like implementation called Ligia using Java, based on communication
via sockets and which includes garbage collection of tuple spaces and agents.
It is also demonstrated how the garbage collection described in [MW97]
is implemented and that it adds little overhead to the overall performance
of the system.
(Postscript
or Postscript (.gz))
This paper concentrates
on a particular KMS --- Case Based Reasoning --- and a particular model
of concurrency --- LINDA.
The extension of Linda to include multiple tuple spaces introduced this new problem as processes are able to create tuple spaces but are unable to delete them or even decide whether a given tuple space is still required in the system or not (garbage).
Techniques for maintaining a structure to be used by a garbage collection algorithm of tuple spaces are described, implemented and the results analysed. Two new concepts are introduced in the model in order to provide the collector with the information required: tuple monitoring and process registration.
Coordination with Attributes
Alan Wood
Coordinatiion Languages and Models: Proceedings of the Third International Conference COORDINATION '99
Springer LNCS-1594, pp 21-36, 1999
Abstract
The development of the idea of coordination languages has enabled work in concurrency to abstract away from the internals of processes or agents and hence to focus on their external interactions. A variety of {\em practical} parallel and/or distributed systems have resulted from the application of the coordination language concept - the most widely-known of these being Linda and its variants.All coordination systems involve a number of logically shared objects, which may themselves be structures containing further objects. In the context of Linda these objects are: tuple spaces, which are bags of tuples each consisting of ordered sequences of atomic elements (in some variants, elements can be non-atomic objects). Tuple spaces are shared between concurrent processes which then coordinate by associatively accessing the tuple spaces. However, in the `classical' Linda model there are no access properties or similar attributes associated with the objects.
This paper addresses the opportunities for, and effects of, incorporating object attributes - primarily those concerned with access-control, but including examples of some less familiar attributes - in Linda-like tuple-space systems. The focus is on exploring how the coordination properties are affected by this enhancement, and investigating in what ways the classical Linda model needs to be modified. Particular emphasis is placed on the potential practical gains to be expected in terms of both performance and expressibility, with consideration being given to methods for implementing attribute frameworks in open distributed systems.
(zipped Postscript (.ps.gz) )
Coordination in a Content-Addressable Web
Ronaldo Menezes, Iain Merrick and Alan Wood
Autonomous Agents and Multi-Agent Systems
vol 2, pp 287-301, 1999
Abstract
The World Wide Web is a very successful phenomenon, and is increasingly being used as a medium for electronic commerce rather than simple information exchange. In this paper it is argued that the low-level infrastructure of the Web is badly suited for these new applications, as well as being somewhat inefficient in its original applications; an alternative infrastructure offering better performance and flexibility is proposed. The new infrastructure is based on the Linda coordination model, and adds a layer of abstraction over the absolute location of resources. Both theoretical and real-world issues are covered, including the problem of integrating this new system with the existing infrastructure of the Web.
Technical Reports
1995
1996ISETL-LINDA: Parallel Programming with Bags.
Andrew Douglas, Alan Wood and Antony Rowstron
YCS 257 (1995).
Abstract
This paper describes the parallel language ISETL-LINDA. The language is an extension of ISETL, an imperative language whose main structure is the set. We extend ISETL by adding a new type of distribute bags, and operations to act on bags which correspond to the LINDA primitives. However, we use a variant of LINDA created at the University of York which replaces the problematic inp and rdp primitives by a single primitive, collect.
(Postscript or Postscript (.gz))
1997On the Implementation of an Asymmetric Hyperspace in Linear Memory: Implementing Tuple Spaces.
Duncan Campbell
YCS 274 (1996).
Abstract
This report sets out the results of an investigation into the distributed implementation of tuple spaces, hence Linda. There are numerous such schemes for implementing distributed tuple spaces, and a selection of these implementations are examined. It is observed that all the implementations have a great deal of similarities. These similarities form the basis for a generalised tuple space implementation, where specific implementations are formed by the appropriate selection of options for various choice points.
(ps.Z)
On a Chemical Abstract Machine for Linda.
Duncan Campbell
YCS 273 (1996).
Abstract
This is a report on the Chemical Abstract Machine (CHAM), and the investigation of its ability to express an abstract machine for Linda. Furthermore, a CHAM for the extended version of Linda which includes the collect() and copy-collect() primitives derived here at York is also investigated. In the light of these investigations, the capabilities of the CHAM are then reassessed, concluding that it is not sufficiently expressive to be able to function as a means for expressing abstract machines for Linda.
(ps.Z)
An efficient distributed tuple space implementation for networks of heterogeneous workstations.
Antony Rowstron and Alan Wood
YCS 270 (1996).
Abstract
The distributed tuple space concept, on which the Linda process coordination model is founded, has given rise to several implementations on parallel machines and networks of heterogeneous workstations. However, the fundamental techniques used in there systems have remained largely unchanged from the original Linda implementations. This paper describes a novel implementation which, using extensions to the original Linda model and recently developed bulk access primitives for tuple spaces, is able to demonstrate 10 to 70 times speed improvements over the best available commercial system. This is achieved dynamically without any compile time optimisations.
(Postscript or Postscript (.gz))
COPY-COLLECT: A new primitive for the Linda model.
Antony Rowstron, Andrew Douglas and Alan Wood
YCS 268 (1996).
Abstract
Linda is a model of communication for concurrent processes. This paper proposes the addition of a new primitive to the Linda model, called copy-collect. An informal semantics of the new primitive is presented and an outline of the {\it multiple rd problem} which provides the justification for adding a new primitive. A description of how the new primitive can be implemented on several different implementations is also provided.
(Postscript or Postscript (.gz))
Coordination using Object Attributes
Alan Wood
YCS 290 (1997)
Abstract
Coordination systems involve a number of logically shared objects which may themselves be structures containing further objects. In the context of Linda, these objects are: tuple spaces, which are bags of tuples each consisting of ordered sequences of atomic elements (in some variants, elements can be non-atomic objects). Tuple spaces are shared between concurrent processes which then coordinate (asynchronously) by depositing tuples in, or associatively retrieving tuples from the tuple spaces. However, in the 'classical' Linda model, there are no access properties or similar attributes associated with the objects (tuple spaces, tuples, and tuple elements).This report addresses the opportunities for, and effects of, incorporating object attributes in Linda-like tuple-space systems. The focus is on exploring how the coordination properties are affected by this enhancement, and investigating in what ways the classical Linda model needs to be modified. Particular emphasis is placed on the potential practical gains to be expected in both performance, and expressibility, with consideration being given to methods for implementing attribute frameworks in open distributed systems.
(Postscript or Postscript (.gz))
Closure for Case Base Retrieval in Linda: an instance of the Iterative Transformation skeleton.
Duncan Campbell
YCS 287 (1997)
Abstract
Linda is a generative communication coordination language, providing communication via tuple spaces (bags of tuples), where tuples may be read/removed from tuple spaces and inserted into them.Case base retrieval is used for case based reasoning (CBR) to retrieve solutions to problems from a set of previously encountered problems and their solutions, or retrieve matching solutions given a template of a desired solution.
In implementing case base retrieval in Linda, closure has been identified as a generic operation, generalising computation patterns in this application, illustrated here in terms of Linda instructions.
The operational semantics of closure are specified in terms of the Chemical Abstract Machine (CHAM) used to specify Liam, the Linda Abstract Machine. This specification is refined in the CHAM to provide the basis for an efficient and parallel implementation of closure as a primitive instruction in Linda, increasing the performance of case base retrieval in Linda.
Furthermore, closure is an instance of the Iterative Combination algorithmic skeleton, itself an instance of the Iterative Transformation algorithmic skeleton. This suggests the addition of Iterative Transformation to the basic classification of algorithmic skeletons, having previously been omitted.
(ps.Z)
Constraint Matching Retrieval in Linda: extending retrieval functionality and distributing query processing
Duncan Campbell.
YCS 285 (1997)
Abstract
Linda is a coordination language using generative communication via tuple spaces, which are global associative memories consisting of bags (or multi-sets) or tuples. The matching of tuples for retrieval has traditionally been undertaken using a simple matching algorithm: performing exact matching or variable substitutions on corresponding elements in a tuple and a tuple template.It is proposed here to generalise the matching process to effectively match according to any function that can be devised as a comparison between tuples. That is, constraint matching, where tuples are matched according to any given constraint.
Constraint matching effectively moves processing from the user process to the individual retrieval instruction. In a distributed Linda environment this means a distribution of the processing associated with complex retrievals to the actual data, thus reducing communication and increasing performance.
Simulations and emulations of constraint matching in the existing specification of Linda are presented. Additionally, the Linda abstract machine, Liam, is modified straightforwardly to support constraint matching instructions. The performance of the constraint matching operation simulations and emulations, and the constraint matching instructions are modelled and compared favourably to the predicted performance.
(ps.Z)
Liam: A Chemical Abstract Machine for Linda.
Duncan Campbell
YCS 282 (1997).
Abstract
Linda is a coordination language using generative communication via a tuple space. This is a global associative memory consisting of a bag (or multi-set) or tuples. There have been proposed at York extensions to Linda's existing repertoire of primitives. These extensions are the collect() and copy-collect() operations, which are bulk retrieval operations that have also been implemented at York.However, though the semantics of Linda have been defined, there are various interpretations, and no one version is generally accepted as standard.
Abstract machines are a means of expressing the operational semantics of a programming language. One particular abstract machine is the Chemical Abstract Machine (CHAM), which is a general formalism that can be instantiated to an abstract machine for a given language. Previous work had suggested that the CHAM was insufficiently expressive to be able to function as a means for fully expressing abstract machines for the basic Linda, and for the bulk operation extensions in particular.
In this report the CHAM is re-examined, investigating its expressing of an abstract machine for the basic Linda. The expressing of an abstract machine for the York extensions with the CHAM is then investigated. This results in the production of just such an abstract machine, called Liam, representing multiple, named tuple spaces, predicated operations and the bulk retrieval operations in addition to the basic Linda operations.
The use of Liam in practice is illustrated here with the specification of a mapping instruction for Linda. Liam illustrates the expressibility of the CHAM, refuting the previous suggestion of its insufficiency. The construction of Liam also suggests implementation strategies for the bulk retrieval operations, particularly the notion of snap-shots.
(ps.Z)
Tuplets: Words for a Tuple Space Machine.
Duncan Campbell
YCS 280 (1997)
Abstract
Linda is a coordination language providing generative communication via tuple spaces. Each tuple space is a global associative memory consisting of a bag (or multi-set) of tuples, where the tuples are variable-sized objects. Repeated insertions and removals of variable-sized tuples are liable to result in the memory containing several small areas of free memory to which larger, variable-sized tuples can not be allocated. This memory redundancy then has to be removed by compacting the memory to produce a large, contiguous area of free memory to which large, variable-sixed tuples can be allocated. Furthermore, when attempting to implement tuple spaces in content-addressable memory (CAM), variable-sized tuples require variable bucket sizes for hash-based schemes. This, along with the need to compare variable-sized blocks of memory when matching, result in implementation problems.In this report, tuplets are proposed as a solution to the problems of variable-sized tuples. Tuplets are fixed-sized tuple components, with each tuple composed of a number of tuplets. Being fixed-sized, tuplet storage behaviour is predictable and manageable. Therefore, only fixed-sized hash buckets are required, and only fixed numbers of words need be compared in hardware CAM schemes.
The central design criterion for tuplets is to associate a key with each tuplet, identifying the tuple of which it is a component, and its location in that tuple.
Various tuplet design and implementation possibilities are considered and examined. Example programs illustrate the implementation of the various tuplet design possibilities. Furthermore, the examples show that the tuplet operations are of comparable complexity to tuple operations, as well as showing a greater potential for parallel execution.
(ps.Z)
Implementing Algorithmic Skeletons for Generative Communication with Linda
Duncan Campbell
YCS 279 (1997)
Abstract
Algorithmic skeletons are seen as being high-level, parallel programming language constructs encapsulating the expression of parallelism, communication, synchronisation, embedding, and costing. Algorithmic skeletons have tended to be presented in terms of message-passing or shared-memory communication models. Here, the application of the skeleton classes in this classification to a generative communication model (Linda) is examined, where it is seen that generative communication does not appear to hold any problems for algorithmic skeletons, and is particularly natural in some cases.This report presents a classification of algorithmic skeletons based on practical experience in the use of such skeletons.
(ps.Z)
Characterising the Design Space for Linda Semantics.
Duncan Campbell, Hugh Osborne and Alan Wood
YCS 277 (1997).
Abstract
Several attempts have been made to produce a (generally adopted) semantics for the generative communication coordination language Linda. However, none has been universally recognised as definitive. Therefore, there are various possible interpretations regarding the semantics of Linda operations.This report presents a survey of a variety of those attempts to produce a semantics for Linda. Also, an attempt is made to identify the areas of confusion which arise, and the possibilities which selecting different choices provide.
(ps.Z)
Ligia: A Java based Linda-like Run-time System with Garbage Collection of Tuple Spaces
Ronaldo Menezes and Alan Wood
YCS 304 (1998)
Abstract
Generative distributed open coordination systems have been so far implemented in a variety of ways. Surprisingly, no published implementation appears to address one particularly important issue for any general purpose open system | garbage collection.This paper describes an open Linda-like implementation called Ligia using Java, based on communication via sockets and which includes garbage collection of tuple spaces and agents. It is demonstrated how to do garbage collection efficiently, showing that little overhead is added to the overall performance of the system.
(ps.Z)