Linda (coordination language)
Encyclopedia
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. Linda was developed by David Gelernter
and Nicholas Carriero at Yale University
and is named for Linda Lovelace
, an actress in the porn movie Deep Throat
, a pun on Ada
's tribute to Ada Lovelace
.
, in which processes store and retrieve tuples.
The original Linda model requires four operations that individual workers perform on the tuples and the tuplespace:
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.
and Fortran, but has since been implemented in many programming languages, including:
Some of the more notable Linda implementations include:
systems. Detailed criticisms of the Linda model can also be found in Steven Ericsson-Zenith's book Process Interaction Models.
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
, Linda is a model of coordination and communication among several parallel processes operating upon objects stored in and retrieved from shared, virtual, associative memory. Linda was developed by David Gelernter
David Gelernter
David Hillel Gelernter is a professor of computer science at Yale University. In the 1980s, he made seminal contributions to the field of parallel computation, specifically the tuple space coordination model, as embodied by the Linda programming system...
and Nicholas Carriero at Yale University
Yale University
Yale University is a private, Ivy League university located in New Haven, Connecticut, United States. Founded in 1701 in the Colony of Connecticut, the university is the third-oldest institution of higher education in the United States...
and is named for Linda Lovelace
Linda Lovelace
Linda Susan Boreman , better known by her stage name Linda Lovelace, was an American pornographic actress who was famous for her performance of deep throat fellatio in the enormously successful 1972 hardcore porn film Deep Throat...
, an actress in the porn movie Deep Throat
Deep Throat (film)
Deep Throat is a 1972 American pornographic film written and directed by Gerard Damiano and produced by Louis Peraino and starring Linda Lovelace ....
, a pun on Ada
Ada (programming language)
Ada is a structured, statically typed, imperative, wide-spectrum, and object-oriented high-level computer programming language, extended from Pascal and other languages...
's tribute to Ada Lovelace
Ada Lovelace
Augusta Ada King, Countess of Lovelace , born Augusta Ada Byron, was an English writer chiefly known for her work on Charles Babbage's early mechanical general-purpose computer, the analytical engine...
.
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 tuplespaceTuple space
A tuple space is an implementation of the associative memory paradigm for parallel/distributed computing. It provides a repository of tuples that can be accessed concurrently. As an illustrative example, consider that there are a group of processors that produce pieces of data and a group of...
, 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
- eval creates new processes to evaluate tuples, writing the result into tuplespace
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
Linda-like systems
Linda-like systems are parallel and distributed programming models that use unstructured collections of tuples as a communication mechanism between different processes.-Examples:...
and implemented as orthogonal technology (unlike original version). An example of this is the language Ease
Ease programming language
Ease is a general purpose parallel programming language, designed by Steven Ericsson-Zenith of Yale University. It combines the process constructs of CSP with logically shared data structures called contexts...
designed by Steven Ericsson-Zenith.
Implementations
Linda was originally implemented in CC (programming language)
C is a general-purpose computer programming language developed between 1969 and 1973 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system....
and Fortran, but has since been implemented in many programming languages, including:
- CC (programming language)C is a general-purpose computer programming language developed between 1969 and 1973 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system....
: C-Linda, TCP-Linda, LinuxTuples - C++C++C++ is a statically typed, free-form, multi-paradigm, compiled, general-purpose programming language. It is regarded as an intermediate-level language, as it comprises a combination of both high-level and low-level language features. It was developed by Bjarne Stroustrup starting in 1979 at Bell...
: CppLinda - Erlang: Erlinda
- JavaJava (programming language)Java is a programming language originally developed by James Gosling at Sun Microsystems and released in 1995 as a core component of Sun Microsystems' Java platform. The language derives much of its syntax from C and C++ but has a simpler object model and fewer low-level facilities...
: JavaSpaces, TSpaces, LightTS, LIME - LispLisp programming languageLisp is a family of computer programming languages with a long history and a distinctive, fully parenthesized syntax. Originally specified in 1958, Lisp is the second-oldest high-level programming language in widespread use today; only Fortran is older...
- Lua: LuaTS
- PrologPrologProlog is a general purpose logic programming language associated with artificial intelligence and computational linguistics.Prolog has its roots in first-order logic, a formal logic, and unlike many other programming languages, Prolog is declarative: the program logic is expressed in terms of...
: SICSus Prolog Linda - PythonPython (programming language)Python is a general-purpose, high-level programming language whose design philosophy emphasizes code readability. Python claims to "[combine] remarkable power with very clear syntax", and its standard library is large and comprehensive...
: PyLindaPyLindaPyLinda is a Python implementation of the Linda coordination language. It is supposed to be a very simple implementation of the Linda distributed computing environment. it supports several newly proposed extensions to Linda like garbage collection, multiple tuple spaces, bulk tuple operations,... - Ruby: RindaRinda (Ruby programming language)Rinda is a software library for creating modular and distributed co-operating services in Ruby using the tuple space or Linda distributed computing paradigm....
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 MPIMessage Passing Interface
Message Passing Interface is a standardized and portable message-passing system designed by a group of researchers from academia and industry to function on a wide variety of parallel computers...
systems. Detailed criticisms of the Linda model can also be found in Steven Ericsson-Zenith's book Process Interaction Models.
See also
- DataflowDataflowDataflow is a term used in computing, and may have various shades of meaning. It is closely related to message passing.-Software architecture:...
- Data flow diagramData flow diagramA data flow diagram is a graphical representation of the "flow" of data through an information system, modelling its process aspects. Often they are a preliminary step used to create an overview of the system which can later be elaborated...
- Dataflow programming
- Flow-based programmingFlow-based programmingIn computer science, flow-based programming is a programming paradigm that defines applications as networks of "black box" processes, which exchange data across predefined connections by message passing, where the connections are specified externally to the processes...
- Programming in the large and programming in the small
External links
- Coordination Language - A small discussion about the differences between the approach of Linda and that of Flow-based programmingFlow-based programmingIn computer science, flow-based programming is a programming paradigm that defines applications as networks of "black box" processes, which exchange data across predefined connections by message passing, where the connections are specified externally to the processes...
- Linda for C++
- Linda for C
- Erlinda (for Erlang)
- Linda for Java
- Linda for Prolog
- PyLinda (for Python)
- Rinda (for Ruby)
- Linda for Scala (on top of Scala Actors)
- Linda in a Mobile Environment (LIME) (for nesCNesCnesC , pronounced "NES-see", is a component-based, event-driven programming language used to build applications for the TinyOS platform. TinyOS is an operating environment designed to run on embedded devices used in distributed wireless sensor networks...
)