Artificial Intelligence and Linda in Context

What to take away

1. 1. The C-Linda dining philosophers solution requires roughly a dozen lines of code, while the canonical Parlog86 solution in Ringwood (1988) requires 70 lines divided across processes cloister, refec, table, cell, finder, and merge, plus five explanatory diagrams—and Ringwood acknowledges that not all code is reproduced.
2. 2. Linda achieved good speedup through 64 nodes on an Intel iPSC/2—the largest machine tested—with implementations based on distributed hash tables that scale with machine size, making continued speedup on larger machines highly likely.
3. 3. Linda has been implemented on at least seven distinct hardware platforms: the Encore Multimax, Sequent Balance, Sequent Symmetry, Alliant FX/8, Intel iPSC/2, S/Net, and Vax/VMS-based local area networks, with ports to additional architectures in progress as of 1989.
4. 4. The C-Linda client-server solution requires no merge process and its code is insensitive to the number of clients, whereas the Parlog86 solution requires a dedicated merge process that explicitly names each client stream, making it unscalable as client count grows from 2 to 20 or 100.
5. 5. For the DNA sequence-comparison problem, Crystal (a pure functional language) produces a marginally shorter specification than C-Linda, but the C-Linda version is an executable parallel program while the Crystal version is a compiler-input specification, making the two strictly incomparable as programs.
6. 6. The 'interpretive abstraction' technique—replacing a fine-grained live data structure with a coarser passive one so that each process fills a sub-block of a matrix rather than a single element—is a programmer-controlled granularity optimization that Carriero and Gelernter demonstrate in C-Linda but argue cannot be performed automatically by functional-language compilers in any demonstrated system.
7. 7. Linda's four core operations (out, eval, in, rd) unify process creation and inter-process communication into a single generative mechanism: eval creates a live tuple that computes and becomes a data tuple, while out creates a data tuple directly, meaning both acts produce the same kind of object in tuple space.
8. 8. A tuple space visualizer built by Paul Bercovitz displays one window per tuple class during execution of the parallel DNA database search (master plus five worker processes), providing a real-time quasi-physical view of how many sequence and result tuples exist at each snapshot—a replicable debugging methodology tied to the tuple-class abstraction identified by a link-time tuple analyzer.
9. 9. The paper raises the open question of whether Crystal-style compiler analysis (targeting SIMD machines like the Connection Machine as well as asynchronous architectures) could automatically determine optimal band granularity for the DNA wavefront computation, noting that achieving this automatically and generally 'strikes us as a difficult problem' that has not yet been demonstrated.
10. 10. Nondeterminism is structurally impossible in pure functional languages, which rules them out entirely for the client-server and dining philosophers problem classes—both of which require whichever process arrives first to claim a resource—while Linda handles nondeterminism naturally through the non-deterministic selection among matching tuples in the in operation.

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 the three dominant paradigms for parallel programming at the time: concurrent object-oriented programming (exemplified by the Emerald system), concurrent logic programming (specifically Parlog86 as presented by Ringwood in a January 1988 Communications article), and pure functional programming (Crystal, targeting SIMD machines including the Connection Machine). The comparison method is direct code contrast on shared benchmark problems: the client-server paradigm, the dining philosophers problem, and a DNA sequence-comparison wavefront computation. Linda itself is defined by four primitive operations—out, eval, in, rd—operating on a generative, persistent, associatively-addressed tuple space that sits outside and orthogonal to whatever base language (C, Fortran, Scheme, Modula-2, PostScript) hosts it. The load-bearing finding is asymmetric: on the problems Parlog86's own advocates chose as showcases, C-Linda is equal or superior. Ringwood's Parlog86 dining philosophers solution runs to 70 lines across six named processes with five explanatory diagrams, while the C-Linda solution is roughly a dozen lines. The Parlog86 client-server merge process must explicitly name every client stream, breaking when client count scales from 2 to 20 or 100, whereas the C-Linda version requires no merge process and is client-count-agnostic. On the functional-language comparison, Crystal produces a marginally more compact specification for the DNA similarity matrix, but the paper argues the comparison is invalid because Crystal code is a compiler input specification, not an executable parallel program; meanwhile, C-Linda achieves demonstrated speedup through 64 nodes on an Intel iPSC/2 using the programmer-controlled 'interpretive abstraction' technique, which replaces fine-grained per-element processes with coarser sub-block processes—a granularity optimization the paper argues no functional-language compiler has yet demonstrated automatically. The paper implies that 'concurrent object-oriented programming' is primarily a marketing label recombining message-passing and monitor-based mechanisms without adding genuine parallel expressivity, that concurrent logic languages embed too much scheduling policy in their primitives, and that functional languages lack the expressivity for nondeterministic resource-contention programs entirely. The prediction is that Linda will prove especially powerful on massively parallel fine-grained asynchronous machines, while acknowledging it does not address SIMD architectures. The most contestable element is the paper's scope of comparison: the Parlog86 and Crystal programs are taken from published advocacy pieces rather than from optimized implementations written by experts motivated to make those languages look good. A critical reader would push back that Ringwood's Parlog86 code was written for pedagogical exposition, not competitive benchmarking, and that selecting 70-line Parlog86 code as the baseline for a brevity comparison systematically flatters Linda. The paper also does not report wall-clock performance numbers for Linda versus Crystal on the DNA problem, only claiming 'good speedup' on the iPSC/2 without specifying absolute runtimes or comparing to Crystal's Connection Machine results on equivalent hardware. An alternative methodological choice—having independent programmers produce best-effort solutions in each language under controlled conditions—would have made the expressivity claims considerably harder to contest.

Findings (5)

• Linda runs on shared-memory (Encore Multimax, Sequent Balance/Symmetry, Alliant FX/8), distributed-memory (Intel iPSC/2, S/Net), and LAN (Vax/VMS) environments.

  Lists the concrete systems on which Linda had been implemented.

• Linda dining philosophers solution uses in/out as counting semaphores; Parlog requires 70 lines across 6 processes with supporting diagrams.
• C-Linda client-server code is insensitive to number of clients; Parlog version requires explicit merge process dependent on client count.
• The Parlog86 solution to dining philosophers consists of 70 lines of code as presented in Ringwood (1988).

  Quantitative observation used to support the claim that Parlog solution is complex.

• C-Linda DNA sequence comparison program is slightly longer than the Crystal version.

  Length comparison of the two programs shown in Figure 3.

Claims (20)

• For DNA database search, it is usually more efficient to run many sequential searches in parallel than to parallelize individual searches.

  Observation from practical experience with DNA sequence comparison.

• Pure functional languages cannot be the whole story for parallel programming because they fail to provide needed expressivity.

  Argument that recursion equations are inappropriate for many important parallel programs.

• Simple problems require systems that expose simple solutions; forcing complex solutions signals misaligned abstraction level.

  Parlog's merge process for client-server is unnecessarily complex; Linda's tuple operations remain flexible across problem variants.

• Forcing complex solutions to simple problems indicates a language has chosen the wrong abstraction level for its primitives.

  General principle illustrated by the dining philosophers comparison.

• The Parlog86 merge process code depends on the number of streams, making it less flexible than Linda for multiple clients.

  Pointing out that Parlog requires explicit, stream-count-dependent merging code.

• Object-oriented design is orthogonal to parallelism; 'objects' themselves do not help with parallel programming.

  Concurrent object systems reduce to message-passing or monitors; objects solve code organization, not concurrency coordination.

• Explicitly parallel programs are not inherently harder to design or understand than functional specifications.

  C-Linda DNA comparison is comparable in length and clarity to Crystal; pragmatic runtime granularity control outweighs compiler optimization ideals.

• Linda unifies process creation, inter-process communication and synchronization within tuple-space operations.

  Key advantage: the same operations handle all three aspects of parallel coordination.

• Uncoupled programming style eliminates the need to know receiver identity, making parallel programming easier.

  Core argument for why Linda's model simplifies parallel programming.

• Achieving automatic parallelization comparable to programmer-controlled granularity is a difficult problem.

  Scepticism about compilers fully automating granularity decisions.

Questions (4)

• Shouldn’t we be tempted to recode these programs in functional languages, flip the autopilot switch, lean back, have a beer, and leave the parallelizing to them?

  Rhetorical question about trusting compilers with parallelization.

• Are the operations that create and control parallelism best left in the programmer’s hands, or should they be turned over to the compiler?

  Central design question underlying the comparison with functional approaches.

• How can a system that differs sharply from all currently fashionable approaches score any kind of success?

  Opening question setting up the paper's purpose.

• Where does it fit, though, and how does it relate to the Big Three?

  Question positioning Linda among the three mainstream parallel models.

Similar preprints — Semantic Scholar