Linda (coordination language)

In computer science, Linda is a model of coordination and communication among several parallel processes operating upon objects stored in and retrieved from shared, virtual, associative memory.[1] It was developed by Sudhir Ahuja at AT&T Bell Laboratories in collaboration with David Gelernter and Nicholas Carriero at Yale University in 1986.[1][2]

Model

This model is implemented as a "coordination language" in which several primitives operating on ordered sequence of typed data objects, "tuples," are added to a sequential language, such as C, and a logically global associative memory, called a tuplespace, in which processes store and retrieve tuples.

The original Linda model requires four operations that individual workers perform on the tuples and the tuplespace:

• in atomically reads and removes—consumes—a tuple from tuplespace
• rd non-destructively reads a tuplespace
• out produces a tuple, writing it into tuplespace (tuple may be duplicated in tuplespace)
• eval creates new processes to evaluate tuples, writing the result into tuplespace

Linda-calculus

The Linda-calculus is a formalisation of the above model with the difference that in the following ${\displaystyle \mathrm {outeval} }$ subsumes both out and eval operations. The presentation of the calculus is based on Cridlig et al.[3]

Syntax

We abstract the concrete representation of tuples. We just assume that we have a set of tuples ${\displaystyle t\in {\mathcal {T}}}$ and we are allowed to form and apply a substitution function ${\displaystyle \sigma }$ on tuples substituting variables for terms that yields a tuple. For example, given we have a tuple ${\displaystyle t=({\mathit {hello}},x)}$, then applying a substitution ${\displaystyle \sigma =\{{\mathit {world}}/x\}}$ on ${\displaystyle t}$ yields ${\displaystyle ({\mathit {hello}},{\mathit {world}})}$

The Linda-calculus processes are defined by the following grammar.

${\displaystyle P,Q::=t\;|\;\mathrm {outeval} (P).Q\;|\;\mathrm {rd} (t).P\;|\;\mathrm {in} (t).P\;|\;P+Q\;|\;\mathbf {rec} X.P\;|\;X}$

The syntax includes the aftermentioned Linda operations, non-deterministic choice, and recursion. The substitution function is extended to processes recursively.

Semantics

A tuple space is represented as a multiset of the processes. We write ${\displaystyle M\,|\,P}$ for ${\displaystyle M\cup \{P\}}$ where ${\displaystyle M}$ is a multiset, ${\displaystyle \{P\}}$ a singleton multiset, and ${\displaystyle \cup }$ is the multiset union operation. The semantics is then defined as a reduction relation on a multiset ${\displaystyle M\rightarrow M'}$ as follows.

${\displaystyle {\begin{array}{lrcll}{\text{(outeval)}}&M\,|\,\mathrm {outeval} (P).Q&\rightarrow &M\,|\,P\,|\,Q&\\{\text{(read)}}&M\,|\,\mathrm {rd} (t).P\,|\,t'&\rightarrow &M\,|\,P\sigma \,|\,t'&{\text{if exists }}\sigma {\text{ such that }}t\sigma =t'\\{\text{(input)}}&M\,|\,\mathrm {in} (t).P\,|\,t'&\rightarrow &M\,|\,P\sigma &{\text{if exists }}\sigma {\text{ such that }}t\sigma =t'\\{\text{(left choice)}}&M\,|\,P+Q&\rightarrow &M\,|\,P&\\{\text{(right choice)}}&M\,|\,P+Q&\rightarrow &M\,|\,Q&\\{\text{(recursion)}}&M\,|\,\mathbf {rec} X.P&\rightarrow &M\,|\,P\{\mathbf {rec} X.P/X\}&\\\end{array}}}$

Note that (input) consumes the tuple ${\displaystyle t'}$ from the tuple space whereas (read) only reads it. The resulting operational semantics is synchronous.

Evaluation

Compared to other parallel-processing models, Linda is more orthogonal in treating process coordination as a separate activity from computation, and it is more general in being able to subsume various levels of concurrency—uniprocessor, multi-threaded multiprocessor, or networked—under a single model. Its orthogonality allows processes computing in different languages and platforms to interoperate using the same primitives. Its generality allows a multi-threaded Linda system to be distributed across multiple computers without change.

Whereas message-passing models require tightly-coupled processes sending messages to each other in some sequence or protocol, Linda processes are decoupled from other processes, communicating only through the tuplespace; a process need have no notion of other processes except for the kinds of tuples consumed or produced (data coupling).

Researchers have proposed more primitives to support different types of communication and co-ordination between (open distributed) computer systems, and to solve particular problems arising from various uses of the model. Researchers have also experimented with various means of implementing the virtual shared memory for this model. Many of these researchers proposed larger modifications to the original Linda model, developing a family of systems known as Linda-like systems and implemented as orthogonal technology (unlike original version). An example of this is the language Ease designed by Steven Ericsson-Zenith.

Implementations

Linda was originally implemented in C and Fortran, but has since been implemented in many programming languages, including:

• C: C-Linda, TCP-Linda, LinuxTuples
• C++: CppLinda, Boreas
• C#: pSpaces
• Erlang: Erlinda
• Go: pSpaces
• Java: JavaSpaces, jRESP, TSpaces, LightTS, LIME, pSpaces
• JavaScript: pSpaces
• Lisp
• Lua: LuaTS Lua Lanes
• Prolog: SICStus Prolog Linda
• Python: PyLinda
• Ruby: Rinda
• Swift: pSpaces

Some of the more notable Linda implementations include:

• C-Linda or TCP-Linda - the earliest commercial and a widespread implementation of virtual shared memory for supercomputers and clustered systems from Scientific Computing Associates, founded by Martin Schultz.
• JavaSpaces - a Java-based tuplespace implementation that helped popularize distributed computing.
• TSpaces - a Java-based tuplespace platform from IBM.

Criticisms

Criticisms of Linda from the multiprocessing community tend to focus on the decreased speed of operations in Linda systems as compared to Message Passing Interface (MPI) systems. While not without justification, these claims were largely refuted for an important class of problems.[4] Detailed criticisms of the Linda model can also be found in Steven Ericsson-Zenith's book Process Interaction Models.[5]

Name

Linda is named after Linda Lovelace, an actress in the pornographic film Deep Throat, a pun on Ada's tribute to Ada Lovelace.[6]

Publications

• Gelernter, David; Carriero, Nicholas (1992). "Coordination Languages and their Significance". Communications of the ACM. 35 (2): 97–107. doi:10.1145/129630.129635.
• Carriero, Nicholas; Gelernter, David; Mattson, Timothy; Sherman, Andrew (1994). "The Linda Alternative to Message-Passing systems". Parallel Computing. 20 (4): 633–655. doi:10.1016/0167-8191(94)90032-9.
• Wells, George. "Coordination Languages: Back to the Future with Linda" (PDF). Rhodes University. Archived from the original (PDF) on 2009-12-19.
• Sluga, Thomas Arkadius. "Modern C++ Implementation of the LINDA coordination language". University of Hannover. Missing or empty |url= (help)

See also

• Dataflow
• Data flow diagram
• Dataflow programming
• Flow-based programming

References

1. Ahuja, Sudhir (AT&T Bell Laboratories); Carriero, Nicholas; Gelernter, David (August 1986), "Linda and Friends", Computer, IEEE, 19b (8): 26–34, doi:10.1109/mc.1986.1663305
2. Carriero, Nicholas; Gelernter, David (1985-01-01). "The S/Net's Linda Kernel (Extended Abstract)". Proceedings of the Tenth ACM Symposium on Operating Systems Principles. SOSP '85. New York, NY, USA: ACM: 160–. doi:10.1145/323647.323643. ISBN 978-0897911740.
3. Cridlig, Régis; Goubault, Eric (1993). "Semantics and analysis of linda-based languages". Lecture Notes in Computer Science, vol 724. Springer, Berlin, Heidelberg. doi:10.1007/3-540-57264-3_30. ISBN 978-3-540-57264-0.
4. Carriero; et al. (1 April 1994). "The Linda Alternative to message-passing systems". Parallel Computing. 2 (4): 633–655.
5. Ericsson-Zenith (1992). Process Interaction Models. Paris University.
6. Markoff, John (January 19, 1992). "David Gelernter's Romance With Linda". The New York Times.

External links

• Coordination Language - A small discussion about the differences between the approach of Linda and that of Flow-based programming
• Linda for C++
• Linda for C
• Erlinda (for Erlang)
• PyLinda (for Python)
• Rinda (for Ruby)
• Linda in a Mobile Environment (LIME) (for nesC)