Site Tools


wiki:sync-linda

Linda

Linda is a coordination model, introduced by David Gelernter in the early 1980s, built around a shared associative memory called a tuple space. Unlike CSP, where processes send messages directly to each other, Linda processes never address one another at all. They only interact with the tuple space: writing tuples into it and reading or removing tuples that match a pattern.

out("task", 42)          // write a tuple into the tuple space
in("task", ?x)            // remove a matching tuple, blocking until one exists
rd("task", ?x)             // like in, but leaves the tuple in the space

The three operations

  • out writes a tuple into the shared space. It never blocks.
  • in searches for a tuple matching a given pattern, removes it, and blocks if no match currently exists.
  • rd is like in but leaves the matched tuple in place, so other processes can still read (or take) it too.

Pattern matching is by shape and value: a query like in("task", ?x) matches any tuple that is a 2-element tuple whose first field is the string "task", binding x to whatever the second field holds.

Decoupling in space and time

Linda's key property is that producers and consumers are decoupled in both space (neither needs to know the other exists, let alone its address) and time (a tuple written before any consumer exists just sits in the tuple space until one shows up and reads it). This is a strictly looser coupling than mailboxes, which are still addressed to a specific recipient even though sender and receiver don't rendezvous synchronously the way CSP channels do. The tradeoff is that a shared associative space is harder to implement efficiently at scale than point-to-point channels, since every in/rd is conceptually a search over everything currently in the space.

wiki/sync-linda.md · Last modified: by 127.0.0.1