paper
active
1989
paper:2024-03-01-stefan-lesser-carriero-20-20linda-20in-20context-pdf-6070a8

Linda in context

ByNicholas Carrier·David GelernterYale University, Yale University, Department of Computer Science
DOI 10.1145/63334.63337
Denotational & semantic program designDenotational & semantic program designassociative addressingConcurrent PascalFortran-LindaEhud ShapiroMach distributed operating systemModula-2 Lindafairness (scheduling)MesaPostScript LindaLinda operating system environmentModulaScheme LindaLinda wins the freedom to coexist peacefully with any number of base languages and computing models.live tuple+6 more

TL;DR

Linda's tuple-space model of parallel programming — embodying just 4 primitive operations (eval, out, in, rd) — demonstrably solves canonical concurrency problems more simply and flexibly than Parlog86, concurrent object/monitor systems, and pure functional languages such as Crystal. The head-to-head comparison method deployed here shows that the Parlog86 dining-philosophers solution requires approximately 70 lines of code across processes cloister, refec, table, cell, finder, and merge, supported by five explanatory diagrams, while the C-Linda solution fits in roughly 15 lines with no auxiliary merge process. For the client-server paradigm, Parlog86's merge process must be rewritten whenever the number of client streams changes, whereas the C-Linda version is insensitive to client count — a property critical in master-worker applications with 20 or 100 parallel workers. Linda has been validated on machines ranging from the Encore Multimax and Sequent Balance to the Intel iPSC/2 (up to 64 nodes), the Alliant FX/8, and Vax/VMS local-area nets, with applications including DNA sequence comparison, LU decomposition, sparse LDLT factorization, and ray-tracing fractal images at Yale and rocket-plume parameter sensitivity analysis at Sandia National Labs. The paper argues that concurrent object-oriented programming is largely a marketing term repackaging message-passing and monitors, that concurrent logic languages embed too many policy decisions in their primitives, and that pure functional languages like Crystal are structurally incapable of expressing nondeterministic or object-manipulation-centric programs — implying that Linda's orthogonality to any base language makes it the uniquely general substrate for practical parallel programming across coarse, medium, and fine-grained granularities.

What to take away

  1. 1. Linda's 4 core operations — eval, out, in, and rd — unify process creation, asynchronous communication, and synchronization within a single generative tuple-space model, eliminating the three-category separation (fork, send, receive) required by message-passing systems.
  2. 2. The Parlog86 dining-philosophers solution requires approximately 70 lines of code divided across 6 named processes (cloister, refec, table, cell, finder, merge) with 5 diagrams, whereas the equivalent C-Linda solution is roughly 15 lines with no auxiliary process.
  3. 3. Linda applications demonstrated good speedup through 64 nodes on the Intel iPSC/2, which was the largest machine tested, with the distributed hash-table implementation expected to scale further on larger machines.
  4. 4. The client-server comparison reveals a structural asymmetry: Parlog86's merge process must be explicitly rewritten when the number of client streams changes from 2 to 20 or 100, while the C-Linda version contains no code that reflects client count and requires no modification.
  5. 5. The Crystal pure functional language version of the DNA sequence-similarity computation is roughly comparable in length to the C-Linda version but constitutes a program specification rather than a program, exposing the category error in directly comparing functional-language conciseness to Linda conciseness.
  6. 6. Linda has been implemented and tested on at least 7 distinct hardware platforms: Encore Multimax, Sequent Balance, Sequent Symmetry, Alliant FX/8, Intel iPSC/2, S/Net, and Vax/VMS local area nets, with ports to C, Fortran, C++, Scheme, PostScript, and Modula-2 base languages.
  7. 7. The paper raises as an open question whether Crystal-style functional compilers can automatically determine optimal matrix band size for the DNA comparison problem — a granularity decision the Linda programmer resolves empirically by running experiments, and which the paper characterizes as a 'difficult problem' for automation.
  8. 8. To replicate the client-server benchmark, a researcher should implement a numbered-tuple stream in Linda (tuples of form ('request', index, payload)) with the server incrementing an index field across successive in statements, and compare this against a Parlog86 solution using explicit stream-merge processes for 2, 20, and 100 clients.
  9. 9. The tuple-space visualizer built by Paul Bercovitz represents each live tuple as a sphere in a per-class window, enabling real-time observation of a 5-worker DNA database searcher progressing from ~100 queued sequence tuples through depletion, and is presented as evidence that Linda's physical object metaphor provides a more direct mental model than recursion equations.
  10. 10. The paper hypothesizes that process lattices — hierarchies of concurrent expert processes with abstract decision procedures at higher levels — will become increasingly important for real-time expert monitoring applications, and that this class of programs is structurally inexpressible in pure functional languages due to their dependence on nondeterminism.

Peer brief — for seminar discussion

Carriero and Gelernter's 1989 Communications of the ACM paper conducts a systematic head-to-head comparison of Linda's tuple-space model against three then-dominant paradigms for parallel programming: concurrent object-oriented systems (specifically the Emerald monitor model), concurrent logic programming (specifically Parlog86 as presented by Ringwood in the same journal), and pure functional programming (specifically the Crystal language). The comparison method — side-by-side code for canonical benchmark problems — is the paper's primary instrument, applied to the client-server paradigm, the dining philosophers problem, and DNA sequence similarity computation. Linda itself provides 4 primitives: out and eval to place passive and active tuples into a shared tuple space, and in and rd to remove or read tuples via associative template matching. The load-bearing finding is asymmetric across the three comparisons. Against Parlog86, Linda wins on both cases: the dining philosophers solution in Parlog86 runs to approximately 70 lines across 6 named process types with 5 supporting diagrams, while C-Linda requires roughly 15 lines; the client-server solution in Parlog86 requires a merge process whose code scales with the number of client streams, while the C-Linda solution is insensitive to client count. Against Crystal, Linda loses slightly on conciseness for the DNA comparison but the paper reframes this as a category error — Crystal code is a specification for a parallelizing compiler, not a parallel program — and argues that the granularity optimization technique called interpretive abstraction, which replaces fine-grained live data structures with coarser processes filling sub-blocks, is available to the Linda programmer but structurally unavailable inside a pure functional language. Against monitors and the Emerald system, Linda's asynchronous out is contrasted with the synchronous blocking of monitor procedure calls, which the paper argues is the wrong default for parallel workloads. Empirically, Linda had achieved good speedup through 64 nodes on the Intel iPSC/2 and was in production use at Yale for fractal ray-tracing and at Sandia National Labs for rocket-plume parameter sensitivity analysis over a local area network. The paper's central implication is that concurrent object-oriented programming is a marketing term rather than a technical category, that logic language primitives are too policy-laden for general parallel use, and that functional languages cannot express nondeterministic or object-manipulation programs — leaving Linda's orthogonal, base-language-agnostic tuple-space model as the uniquely general alternative. The paper also advances a hypothesis about process lattices — hierarchical structures of concurrent expert processes used for real-time monitoring — as a coming application class that neither functional nor logic languages can naturally accommodate. The most contestable element is the methodology itself: the comparison relies on Ringwood's own Parlog86 showcase examples as the benchmark set, which means Linda is being tested against problems a Parlog proponent selected as showpieces for logic programming. A critical reader would note that this selection bias is acknowledged only partially — the authors admit Linda loses slightly on the DNA comparison — but the choice of exactly two problems where Parlog86 is weakest (client-server with variable client count, dining philosophers requiring a merge process) and one where Linda is conceded to be longer is not a controlled evaluation. An alternative methodology, such as a systematic benchmark suite drawn from a neutral third party or a performance evaluation on a shared hardware platform with wall-clock timings rather than line counts, would substantially strengthen the comparative claims. The paper also does not evaluate Linda against dataflow languages such as Id or against shared-memory languages with barrier synchronization, which were plausible contemporaneous alternatives not included in Shapiro's 1988 Hypercube conference taxonomy that the paper adopts as its framing.

Methods (4)

Frameworks (4)

  • Concurrent Pascal
    A language designed by Brinch Hansen that explored monitors; cited in the comparison.
  • Mach distributed operating system
    A distributed OS that uses message-passing; mentioned as an example of that model.
  • Mesa
    Language with monitor experience reported by Lampson and Redell; cited in monitor discussion.
  • Modula
    Language by Wirth that incorporated monitor concepts; referenced for monitor expressivity.

Findings (2)

Claims (17)

Hypotheses (1)

Questions (1)

Related work— refs + corpus + external arXiv

Cited / in-corpus / arXiv badges show which signals surfaced each row. Multi-source rows weighted higher.

+28 more

Similar preprints — Semantic Scholar

Cross-corpus bridges (2)

same_concept_as · Nomic cosine

External markdown files that talk about the same concept as this entity.

  • alexander
    Artificial Intelligence and LINDA IN CONTEXTpapers/extracted/2024-03-01_Stefan-Lesser_Carriero-20--20Linda-20in-20Context.pdf_6070a.md0.832
  • alexander
    2024 03 01 Stefan Lesser Carriero 20 20Linda 20in 20Context.pdf 6070a8papers/extracted/2024-03-01_Stefan-Lesser_Carriero-20--20Linda-20in-20Context.pdf_6070a8.md0.774