Linda

Introduction

Linda is a concurrent programming model that has evolved from a Yale University research project. The primary concept in Linda is that of a tuple space, an abstraction via which processes communicate. This central theme of Linda has been proposed as an alternative paradigm to the two traditional methods of parallel processing, that based on shared memory, and on message passing. [1]

Difference with message passing

This model differs from the message passing model in requiring that messages be added in the tuple space where they exist independently until a process chooses to remove them. A process generates an object called a tuple and places it in the tuple space. Theoretically, the object remains in tuple space forever, unless removed by another process.

Kinds of tuples

Tuple space holds two varieties of tuples. Process or "live" tuples are under active evaluation, incorporate executable code, and execute concurrently. Data tuples are passive, ordered collections of data items. For example, the tuple ("mother","age",56) contains three data items: two strings and an integer. A process tuple that is finished executing resolves into a data tuple, which may in turn be read or consumed by other processes [2]

Primitives

The primitives used in Linda are the following:

  • out: out(t) adds tuple t to tuple space.
  • in: in(t) attempts to match some tuple t in tuple space to the template m and, if a match is found, removes t from tuple space.
  • rd: rd(t) Similar to in except that the matched tuple remains in tuple space. The executing process suspends if it fails to match a tuple.
  • eval(expression) Similar to out except that the tuple argument to eval is evaluated after t is added to tuple space.

Examples

  • out("sum", 2,3) : adds this tuple into the tuple space and process it immediately.
  • in("sum",?i,?j) : matches "sum", assigns 2 to i and 3 to j and the tuple is removed from the tuple space.
  • rd("sum",?i,?j): matches "sum", assigns 2 to i and 3 to j but the tuple is not removed from the tuple space.
  • eval("ab",-6,abs(-6)): creates or allocates another process to compute the absolute value of -6. Once evaluated, the active tuple resolves into the passive tuple ("ab",-6,6), which can now be consumed or read by an in or rd.
  • eval("roots",sqrt(4),sqrt(16)): This creates a live tuple. The square-root operations are performed independent of the originating process, with the (two) numeric results combined to form a three element tuple saved in tuple-space.

Data types

Tuple members are usually simple data types: characters, one-dimensional strings, integers, or floats. In some Linda implementations tuples can include more complex data types (e.g., integer arrays). These data structures are removed from or added to tuple space just like the more fundamental types.

++Java Implementations of Linda
Linda is designed to be integrated with a sequential programming language (called the host language, e.g Java). One of the first implementations was the development of JavaSpaces[3] by Sun Microsystems.

Operations

Operations that insert or withdraw from tuple space do so atomically. In theory, nondeterminism is inherent; it is assumed that the tuples are unordered in tuple space so that, given a template m and matching tuples t1, t2, and t3, it can not be determined which tuple will be removed by in(m). In practice, implementations of tuple space fall short of pure nondeterminism. Some ordering is inescapable but remains implementation-dependent. It is in the spirit of Linda programming not to presuppose any ordering of tuples in the underlying mechanism. Sequencing transactions upon tuple space is facilitated using a sequencing key as an additional tuple element, a method employed to program distributed arrays in Linda.

Properties

Several properties distinguish Linda. Generative communication simply means that a tuple generated by process p1 has independent existence in tuple space until removed by some process p2. This property facilitates communication orthogonality because a receiver has no prior knowledge about a sender and a sender has none about the receiver—all communication is mediated through tuple space. Spatial and temporal uncoupling also mark Linda. Any number of processes may retrieve tuples, and tuples added to tuple space by out remain in tuple space until removed by in.
A property called structured naming deserves special consideration. Given the operations out(t1) and in(m1), all actuals in t1 must match the corresponding actuals in m1 for matching to succeed. The actuals in t1 constitute a structured name or key and, loosely speaking, make tuple space content addressable. For example, if ("sum",10,9) is a tuple in tuple space, then the success of the operation in(“sum”,?x,10) is predicated upon the structured name ["sum'",10]. We are reminded both of the restriction operation in relational databases and instantiation in logic languages. The structured name should not be confused with the logical name, which is simply the initial element in a tuple and must be an actual of any type.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-Share Alike 2.5 License.