Linda (coordination language)

Linda
Paradigm	Multi-paradigm
Family	Coordination language
Designed by	David Gelernter
Developer	Scientific Computing Associates
First appeared	1986; 38 years ago
Website	lindaspaces.com
Influenced
	Java

In computer science, Linda is a coordination model that aids communication in parallel computing environments. Developed by David Gelernter, it is meant to be used alongside a full-fledged computation language like Fortran or C where Linda's role is to "create computational activities and to support communication among them".^[3]^[4]^[5]

History

David Gelernter wrote the first version of Linda as a Ph.D. candidate in 1979, naming it after Linda Lovelace, who appeared in the pornographic film Deep Throat. At the time, the main language for parallel processing was Ada, which Gelernter considered an "inelegant and bulky" language.^[6]

It was widely released in 1986, when Gelernter, along with his Yale colleague Nicholas Carriero and Sudhir Ahuja at AT&T Bell Laboratories, published "Linda and Friends" in an IEEE journal.^[7]

By the early 1990s, Linda was widely used by corporations to more efficiently conduct big data analyses, including Wall Street brokerages as well as AT&T, Boeing, and United Technologies. There were even companies that specialized in creating specialized parallel computing applications based on Linda, the largest of which was Scientific Computing Associates, a New Haven-based company founded by several Yale computer scientists (Gelernter occasionally consulted for them but did not work there).^[6] Interest in Linda dropped in the mid-1990s, only to make a comeback in the late 1990s with several corporations implementing Linda in Java, including Sun Microsystems and IBM.^[3]

Overview

Model

The Linda model provides a distributed shared memory, known as a tuple space because its basic addressable unit is a tuple, an ordered sequence of typed data objects; specifically in Linda, a tuple is a sequence of up to 16 typed fields enclosed in parentheses". The tuple space is "logically shared by processes" which are referred to as workers that store and retrieve tuples.^[8]

Operations

One of Linda's main advantages is that it's simple, with only six operations that workers perform on the tuples to access tuplespace:^[9]

out: Puts a tuple into the tuplespace
in: Takes out a tuple that matches a given pattern from the tuplespace (if there's no match, the operation is blocked)
rd: Copies a tuple that matches a given pattern from the tuplespace (if there's no match, the operation is blocked)
eval: Creates a new process to evaluate tuples
inp: A non-blocking version of in (if there's no match, an error message is returned)
rdp: A non-blocking version of rd (if there's no match, an error message is returned)

Comparison

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. 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.^{[citation needed]} While not without justification, these claims were largely refuted for an important class of problems.^[10] Detailed criticisms of the Linda model can also be found in Steven Ericsson-Zenith's book Process Interaction Models.^[11]

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.^{[citation needed]} Researchers have also experimented with various means of implementing the virtual shared memory for this model.^{[citation needed]} 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.

Linda's approach has also been compared to that of flow-based programming.^[12]

Linda-calculus

The Linda-calculus is a formalisation of the above model with the difference that in the following $\mathrm {outeval}$ subsumes both out and eval operations.^[13]

Syntax

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

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

$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 $M\,|\,P$ for $M\uplus \{P\}$ where $M$ is a multiset, $\{P\}$ a singleton multiset, and $\uplus$ is the multiset union operation. The semantics is then defined as a reduction relation on a multiset $M\rightarrow M'$ as follows.

${\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 $t'$ from the tuple space whereas (read) only reads it. The resulting operational semantics is synchronous.

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.^{[undue weight? – discuss]}

References

^ Ciancarini, Paolo. "Lecture 3: Coordination languages" (PDF). University of Bologna. Retrieved 9 January 2022.
^ "David Gelernter, B.A. & M.A. '76". Yale Scientific. 14 February 2011. Retrieved 8 January 2022.
^ ^a ^b Wells, George (July 2005). "Coordination Languages: Back to the Future with Linda" (PDF). Conference: 2nd International Workshop on Coordination and Adaptation Techniques for Software Entities. Rhodes University. Archived from the original (PDF) on 19 December 2009.
^ Gelernter, David; Carriero, Nicholas (February 1992). "Coordination Languages and their Significance" (PDF). Communications of the ACM. 35 (2): 97–107. doi:10.1145/129630.129635. S2CID 7748555.
^ 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. SOSP '85. New York, NY, USA: ACM. pp. 160–. doi:10.1145/323647.323643. ISBN 978-0897911740. S2CID 6922183.
^ ^a ^b Markoff, John (19 January 1992). "David Gelernter's Romance With Linda". The New York Times. Archived from the original on 30 December 2019. Retrieved 8 January 2022.
^ Ahuja, Sudhir; Carriero, Nicholas; Gelernter, David (August 1986), "Linda and Friends", Computer, 19b (8), IEEE: 26–34, doi:10.1109/mc.1986.1663305, S2CID 5155678
^ John H. Reynolds (December 2002). "Linda arouses a Sleeping Barber" (PDF). Proceedings of the Winter Simulation Conference. Vol. 2. San Diego, CA: IEEE. pp. 1804–1808. doi:10.1109/WSC.2002.1166471. ISBN 0-7803-7614-5. S2CID 62584541. Retrieved 8 January 2022.
^ Masatoshi Seki (February 2017). The dRuby Book: Distributed and Parallel Computing with Ruby (0.1 ed.). Pragmatic Programmers. Retrieved 9 January 2022.
^ Carriero; et al. (1 April 1994). "The Linda Alternative to message-passing systems" (PDF). Parallel Computing. 2 (4): 633–655. doi:10.1016/0167-8191(94)90032-9.
^ Ericsson-Zenith (1992). Process Interaction Models. Paris University.
^ J. Paul Rodker Morrison (2 July 2004). "Coordination Language". Archived from the original on 2023-09-28. Retrieved 9 January 2022.
^ 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.

[lecture-1] Ciancarini, Paolo. "Lecture 3: Coordination languages" (PDF). University of Bologna. Retrieved 9 January 2022.

[scientific-2] "David Gelernter, B.A. & M.A. '76". Yale Scientific. 14 February 2011. Retrieved 8 January 2022.

[wells-3] Wells, George (July 2005). "Coordination Languages: Back to the Future with Linda" (PDF). Conference: 2nd International Workshop on Coordination and Adaptation Techniques for Software Entities. Rhodes University. Archived from the original (PDF) on 19 December 2009.

[coordination-4] Gelernter, David; Carriero, Nicholas (February 1992). "Coordination Languages and their Significance" (PDF). Communications of the ACM. 35 (2): 97–107. doi:10.1145/129630.129635. S2CID 7748555.

[5] 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. SOSP '85. New York, NY, USA: ACM. pp. 160–. doi:10.1145/323647.323643. ISBN 978-0897911740. S2CID 6922183.

[nyt-6] Markoff, John (19 January 1992). "David Gelernter's Romance With Linda". The New York Times. Archived from the original on 30 December 2019. Retrieved 8 January 2022.

[:0-7] Ahuja, Sudhir; Carriero, Nicholas; Gelernter, David (August 1986), "Linda and Friends", Computer, 19b (8), IEEE: 26–34, doi:10.1109/mc.1986.1663305, S2CID 5155678

[barber-8] John H. Reynolds (December 2002). "Linda arouses a Sleeping Barber" (PDF). Proceedings of the Winter Simulation Conference. Vol. 2. San Diego, CA: IEEE. pp. 1804–1808. doi:10.1109/WSC.2002.1166471. ISBN 0-7803-7614-5. S2CID 62584541. Retrieved 8 January 2022.

[9] Masatoshi Seki (February 2017). The dRuby Book: Distributed and Parallel Computing with Ruby (0.1 ed.). Pragmatic Programmers. Retrieved 9 January 2022.

[mpi-10] Carriero; et al. (1 April 1994). "The Linda Alternative to message-passing systems" (PDF). Parallel Computing. 2 (4): 633–655. doi:10.1016/0167-8191(94)90032-9.

[process-11] Ericsson-Zenith (1992). Process Interaction Models. Paris University.

[12] J. Paul Rodker Morrison (2 July 2004). "Coordination Language". Archived from the original on 2023-09-28. Retrieved 9 January 2022.

[13] 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.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]