Many conventional distributed-memory programming systems allocate one process to each node of a multicomputer. The nodes send messages directly to each other. A problem with such systems is that data structures are not global, but rather are localized in each process. One of the most common programming techniques is to manipulate a data structure, but when trying to use that technique on most distributed-memory systems, the data structure must be partitioned and the parts hidden in a fixed number of processes, which creates an artificiality and complexity in parallel programs.
A candidate for a more natural parallel programming system is Linda [AHUJ86] [CARR89a] [CARR89b] [GELE85] [LELE90] which provides a shared associative memory, the tuple space. A tuple is a sequence of fields, each of which has a type and contains a value or a variable.
Tuples are written into the tuple space with an out operation, are removed with an in, and are read without being removed with a rd. For an in or rd, the tuple accessed in tuple space must match the tuple provided with the command. The number and types of fields must be identical. A value must match an identical value. A variable in either must match a value in the other. A variable will not match a variable. The in or rd will block until there is a matching tuple in tuple space. Recent implementations of Linda have provided non-blocking versions or rd and in, rdp and inp, which return a Boolean indication of success.
Linda also has the command eval, which will start a process, an "active tuple," which will return its value by becoming a normal tuple.
Various implementations of Linda have restricted the format of tuples, or the implementation of eval, or have provided multiple tuple spaces.
The tuple space does allow data structures to be shared among processes, and the designers of Linda are quick to point out the advantages of being able to design programs around the shared data structures. Still, a question persists: why does tuple space suddenly become a natural structure for parallel programming when there was no demand for it in sequential programs? An examination of the published Linda fragments suggests an explanation: in almost all cases the tuple space is being used as a shared, flat directory of queues. Since both directories and queues have long been known to be useful in multiprogramming and multitasking systems and since they can so easily be implemented in tuple space, it is no surprise that Linda is successful. But this does suggest that a system built directly on a shared directory of queues might work as well as or better than Linda and that clarity on the data structures actually being used might suggest useful facilities that tuple space would not suggest.
The Memo System (Memo) was designed and implemented to investigate the possibilities for a parallel programming system built around a shared directory of queues.
AHUJ86 Ahuja, Sudhir, Nicholas Carriero, and David Gelernter, "Linda and Friends," IEEE Computer, Aug. 1986.
CARR89a Carriero, Nicholas, and David Gelernter, "Linda in Context," CACM, 32:4, Apr. 1989.
CARR89b Carriero, Nicholas, and David Gelernter, "How To Write Parallel Programs: A Guide to the Perplexed," ACM Computing Surveys, 21:3, Sep. 1989.
GELE85 Gelernter, David, "Generative Communication in Linda," ACM TOPLAS, 7:1, Jan. 1985.
LELE90 Leler, Wm, "Linda Meets Unix," IEEE Computer, Feb. 1990.