Generative Communication in Linda

Generative Communication in Linda – Gelernter 1985

This is the second of five papers selected by Peter Alvaro as part of his ‘Desert Island papers’ nominations.

Generative communication is the basis of a new distributed programming language called Linda… Where most distributed languages are partially distributed in space and nondistributed in time, Linda is fully distributed in space and distributed in time as well. Linda appears in many cases to be both simpler and more expressive than existing proposals within the application domains of interest.

After monitors (shared variables), message passing, and remote operations, Linda represents an often forgotten fourth model of concurrent programming, and Gelernter makes a forceful case for it. You may know the ideas behind Linda as the concept of a Tuple Space, or from JavaSpaces. A Linda program is a collection of ordered tuples, and an executing Linda program occupies an environment called a “tuple space” (TS). Many concurrent processes make up a distributed Linda program, and all are encompassed within one tuple space.

This communication model is said to be generative because, until it is explicitly withdrawn, the tuple generated by A has an independent existence in TS. A tuple in TS is equally accessible to all processes within TS, but is bound to none.

This paper is concerned with the three basic operations defined over TS; out for adding a tuple; in for withdrawing a tuple; and read to read one without withdrawing it. From these simple primitives, a wide variety of program designs can be easily expressed as we shall see. A fourth primitive eval is not discussed in this paper, but you can read about it in Linda in Context – eval starts a concurrent process which evaluates to a tuple which is then added to TS. Use of eval can generate ‘live data structures.’

Let us first review how Linda works, then examine some of its properties through a series of simple examples.

Linda’s operations

out(tuple) – execution of the out statement results in the insertion of the tuple into TS; the executing process continues immediately. The first element of the tuple is a string identifier (a name that acts as an identification tag).
in(N, P2, … , Pj) – N is the identification tag, P2..Pj may be either actual parameter values, or ‘formals’ (variables). Linda uses parameter matching to find and withdraw a matching tuple in TS and bind tuple components to any formals. The expression executing the in statement then continues. If there is no matching tuple available, then in suspends until one is available.
read(N, P2, … ,Pj) behaves as in, but the matched tuple is not withdrawn from TS.

Gelernter calls the parameter matching of Linda ‘structured naming.’ Some examples:

in(tag, i: integer, j:boolean)

matches any 3-tuple with ‘tag’ that has an integer as its second component, and a boolean as its third. Binds these values to i and j respectively.

in(tag, 2, j:boolean)

matches any 3-tuple with ‘tag’, with the value 2 as its second component, and a boolean as its third. Binds the boolean value to j.

in(tag, i:integer, FALSE)

matches any 3-tuple with ‘tag’, with the value FALSE as its third component, and an integer as its second. Binds the integer value to i.

And so on…

Structured naming is similar in principle to the “select” operation in relational database systems, and may be said to make TS content-addressable. It also resembles in a rudimentary but significant way the pattern-matching features that are part of some AI and logic languages, particularly Prolog.

out tuples may also contain formals – these can only be matched by actual values in an in statement. This is referred to as inverse structured naming.

Linda has four composed statements: sequence, and, or, and star. A sequence s1; s2; … ; sn executes s1..sn sequentially.

An and statement s1 & s2 & … & sn specifies that s1, … sn have concurrent lifetimes. If one or more of the statements are variable declarations, then the the declared variable exists for as long as the compound statement executes.

An or statement s1 | s2 | … | sn specifies that s1…sn have mutually exclusive lifetimes. A single enabled constituent of the or-statement is chosen for execution.

The star statement *s executes ‘s’ zero or more times. A star-statement of the form

*[in(t); s]

where s is any statement is referred to as an in-block, and is so common that the shorthand notation

    in(t) => s

may be used instead.

Distinguishing properties of Linda

Linda has communication orthogonality. It’s possible to use tuples to communicate between a sender and a receiver, but neither party directly knows about the other. This leads to two fundamental properties of the Linda model: space uncoupling, and time uncoupling.

Space uncoupling (distributed naming). Distributed naming refers to the fact that a tuple in TS tagged “P” may be input by any number of address-space-disjoint processes. In particular, j processes executing on j distinct network nodes may all accept tuples tagged with one name. Distributed naming means that Linda is fully distributed in space.

(In other words, a tuple space is a transparently distributed data structure).

Time uncoupling. A tuple added to TS by out( ) remains in TS until it is removed by in( ). If it is never removed by in( ) it will, in the abstract, remain in TS forever. In practice, tuples added to TS by a given distributed program will be removed once all that program’s processes have terminated, unless the programmer indicates explicitly to the contrary. Despite these practical considerations, Linda allows programs to be distributed in time insofar as process A in which some out( ) statement appears may run to completion before process B, in which the corresponding in( ) appears, is loaded.

These two properties combine to support distributed sharing. Several processes may share some variable by depositing it in TS. The TS-operator definitions ensure that v will be maintained atomically.

Continuation passing styles are supported by posting a tuple and then blocking in expectation of a reply – or even continuation in some third process.

Structured naming allows in and read statements to restrict, and out statements to widen, their focus.

Examples

An RPC:

    // caller
    out(P, me, out-actuals);
    in(me, in-formals)

    // receiver
    in(P, who:name, in-formals) => 
        [ body of procedure P;
          out(who, out-actuals) ]

A semaphore:

    // resource owner on initialization, 
    // repeat n times for n resources
    out(sem)

    // to use resource
    in(sem);
    work with resource
    out(sem);

Master-slave:

    // master posting job k
    out(idle, k)

    // slaves
    in(idle, j:job_description)

Filtering examples in the paper involve putting an intermediary between clients and an ultimate server. Clients post a tuple as in the RPC example. A ‘filter’ process reads this tuple and passes it onto the server (by posting it with an internal tag the server is looking for) if/when it chooses. These filters can implement queueing, throttling etc..
Sticky sessions:

    // server protocol
    in(server, U:name, start);
    [then for the duration of the conversation]
    in(server, U, r:request)

    // client protocol
    out(server, me, start);
    out(server, me, request)   // repeat as needed

Global variable:

    read(var_name, v:value)

Dining philosophers (from the Linda in context paper):

    // initialization
    for (int i = 0; i < Num; i++) {
        out("chopstick",i);
        eval(phil(i));
        if (i < (Num-1)) out("room ticket");
    }
    
    // philosophers
    phil(i) 
     int i;
    {
        while(1) {
          think();
          in("room ticket");
          in("chopstick",i);
          in("chopstick",(i+1)%Num);
          eat();
          out("chopstick",i);
          out("chopstick",(i+1)%Num);
          out("room ticket");
        }
    }

the morning paper

a random walk through Computer Science research, by Adrian Colyer
Made delightfully fast by strattic

Generative Communication in Linda

Linda’s operations

Distinguishing properties of Linda

Examples

Further reading