On the Implementation of an Asymmetric Hyperspace in

Linear Memory:

Implementing Tuple Spaces

Duncan K. G. Campbell

Department of Computer Science

University of York

November 29,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.

1 Introduction

1.1 Linda

Linda[Gel85, CG89] is a coordination language providing communication via tuple space, which is a global associative memory consisting of a bag (or multi-set) of tuples. Tuples are of two sorts: passive (tuple elements are data only) and active (tuple elements are functions). When the functions of an active tuple have completed, a passive tuple replaces it. The following operations operate on tuple space:

out(t) takes a (passive) tuple, t, (containing only actual arguments) and places it into the tuple space, returning immediately;

in(t) takes a tuple template, t, (containing actual and/or formal arguments), and if it matches a tuple in the tuple space the matching tuple is removed from the tuple space and returned to the calling process (with appropriate instantiation of formal arguments). If there is no match available, this will block;

rd(t) is like in(t) but returns only a copy of a matching tuple from the tuple space rather than removing it;

eval(t) is Linda's process creation mechanism, taking an active tuple, t, and placing it into the tuple space, returning immediately. The process finishes by returning a passive tuple in tuple space. The active tuple can not be retrieved from tuple space, unlike passive tuples.

Hence, Linda provides generative communication, that is communication by the production and consumption of passive data structures.
There are also the following predicated operations, which are not always considered a part of Linda: