An implementation of
AssociativeMemory that provides a repository (mathematically a
bag) for tuples,
generatively.
- TupleSpace is a really shared memory because any process can reference any Tuple regardless of where that Tuple is stored.
- TupleSpace is a logically shared memory because it provides the appearance of a shared memory but does not require an underlying physical shared memory.
- TupleSpace is also an AssociativeMemory, which means that tuples are accessed not by their address but rather by their content and type.
- The TupleSpace communication model is termed generative (see: GenerativeCommunication) because a tuple generated by a process has an independent existence in TupleSpace. Any process may remove the tuple, and the tuple is bound to no process in particular.
The concept of tuple space was pioneered by
DavidGelernter at the
YaleLindaGroup and was initially offered in
FortranLanguage and
CeeLanguage languages. However, various other
TupleSpace systems exist today such as LiPS or Actor
Spaces for many languages including the
SmalltalkLanguage,
JavaLanguage,
LispLanguage and
RubyLanguage (
DistributedRuby). For some reason, the
JavaLanguage is experiencing an explosion of generative systems including
JavaSpaces, TSpace, Page
Spaces,
OpenSpaces, and so on.
For criticisms of the
TupleSpace model relative to ConcurrentLogicProgramming
?,
MessagePassingConcurrency and
CommunicatingSequentialProcesses, see
https://www.cypherpunks.to/erights/history/clp/linda-letters.pdf (starting on page 4 of the PDF).
The tuple spaces model of concurrency originated at Yale with the
LindaTupleSpaces system - a co-ordination language for expressing parallel processing, whose strength lies in its ability to describe parallel algorithms without reference to any specific computer architecture.
The key feature of
LindaTupleSpaces is that it provides inter-process co-ordination via virtual shared memories (tuple-spaces) which are accessed associatively. By incorporating the
LindaTupleSpaces primitives and tuple-spaces (`bags' of tuples) into a programming language, algorithms developed using the model can be more easily ported between different parallel computers. It is this ability to
abstract away from particular computational structures that makes the tuple-space model a particularly attractive vehicle for parallel algorithm and architecture research.
What is a Tuple?
A tuple is a fixed fixed-length list containing elements that need not have the same type. It can be, and often is, used as a key-value pair.
An introduction to tuple spaces:
http://www-unix.mcs.anl.gov/dbpp/text/node44.html
Is it a requirement that all elements of a tuple be ValueObjects or otherwise have reasonable value-semantics? In other words, putting ReferenceObjects in a tuple is a no-no?
I might not be the correct person to answer this, since I often use languages where the distinction between the two is not clear (unlike Java), but that gives you a good answer: depends on the language environment. The border goes in mutability, not referencing model - mutable data structures may incur some problems that subvert some of the benefit for using tuple spaces. Because the tuples in a tuple space are often indexed, having mutable values in them is similar to mutable hash keys.
Related:
TupleDefinition
Implementations of TupleSpaces
Ruple represents a new kind of tuple space. Instead of a tuple, the entries are well-formed, but not necessarily validated, XML documents.
The current implementation of Ruple leaves a lot to be desired. But more implementations along the same lines should appear by 2003, open source and commercial.
"XML Documents" in this case may be large or small. They may be formal or semi-formal. They may represent a business or domain document, or they may represent nearly pure control information for automated processing, following well-known TupleSpacePatterns
?.
Discussion
Sounds a lot like a relational database!
It is much different, in so many ways. It's not even like an Object Database. For example, a
TupleSpace uses associative lookup. In fact, most programmers unfamiliar with the GenerativeIdiom
? become passionately disappointed when they find that they cannot use a
TupleSpace system (such as
JavaSpaces) as a traditional object database.
Hmm? I certainly is different from an object database, but it is relatively similar to a relational database (in the data model). It is meant for different things, though. Tuple spaces give you more power to make your own structure, whereas relational databases provide full-featured query languages...
As I understand it, it's primarily a way of doing distributed computing based on a BlackboardMetaphor. --
AnonymousDonor
I'd say that's certainly true. And while
TupleSpace is more of a parallel-programming idiom, it's great for distributed systems. However,
TupleSpace is nothing more than an implementation of
AssociativeMemory. In this light, I would switch around your statement a little to say:
-
- Systems based on the BlackboardMetaphor can be simply created in TupleSpace.
Using the previous wording implies that
TupleSpace is limited to systems that use this metaphor. Because I wouldn't describe
AssociativeMemory as a Blackboard System, I wouldn't describe
TupleSpace as one either. In fact, because its design is so perfectly simple, it is hard to find a single predominate use of the generative idiom -- it works well for solving many different types of parallel-programming problems and distributed systems. However,
one of the
more popular uses of
TupleSpace (
AssociativeMemory) is for implementing a
ComputeServer which is more general than the
BlackboardMetaphor (which has specialists grabbing information scoped to their specialty).
A good example of the
ComputeServer pattern is the
SetiAtHome screen saver project (
http://setiathome.ssl.berkeley.edu/sciencepaper.html).
SetiAtHome uses multiple, autonomously collaborating unskilled workers (your computer in screen saver mode) that continually grab tasks (figures to be analyzed), process them, and return the results to an
AssociativeMemory (i.e. SETI).
With a
ComputeServer, processes posting tasks, processes retrieving results, and processes that are removing and executing Tasks from
AssociativeMemory operate collaboratively but autonomously -- they aren't aware of each other. One can bring on new workers without disturbing the system. Adding a new processor will usually result in increased performance. You also see this style used a lot in crypto-analysis. Unlike the
BlackboardMetaphor, the algorithm is specialized within the actual Task Tuple. --
RobertDiFalco
I am a HUGE fan of tuple spaces. They are the most powerful execution environment there is, since the guillotine has gone out of favor. No contest. I believe it can be optimally configured to model any execution environment. Static binding, no problem, dynamic binding, no problem, distribution, no problem, transactions, no problem, persistence, no problem, and so on. These Yale guys are sitting on a gold mine. All we need is a fast O/S mapping and this would take over. No doubt. Word :). --
RichardHenderson
A gold mine? Does YaleUniversity (or anyone else for that matter) hold patents on TupleSpace?
Do you have any favourite introduction to
TupleSpaces? I've just started learning about them, and the best doc I've found so far is
Linda in Context,
http://www.cs.uwaterloo.ca/~fmavadda/p444-carriero.pdf (haven't finished it yet, and I'd prefer a little less context ;-)) --
LukeGorrie
JavaSpacesPrinciplesPatternsAndPractice (Freeman, Hupfer, Arnold) is a very good introduction to tuple spaces in general, even though it is centered around
JavaSpaces which is a bit different. --
AndersBengtsson
Found out a nice introduction here
http://phi.sinica.edu.tw/instruct/workshop/html/linda/linda.html
--
AravindAjad
Discussion
Could someone articulate the difference between a message queue and a tuple space for me? It seems as though all of the functionality inherent in a message queue could be implemented using a tuple space. Is this accurate?
Messages go from one person to another. Tuple Space is a bag with tuple in it. Whereas only the intended recipient of a message gets to see it, the tuples in Tuple Space can be read, "received" and processed by anyone.
By adding an intended recipient's name as a field in a tuple you can implement messages via tuple space, but that's like saying you can implement Python on a
TuringMachine. True, but not necessarily helpful.
MessageQueue has ordering of the messages, which is not necessarily maintained by tuple space. It is possible to force sequencing of messages by including a time, matching on all messages for me, then selecting the message with the earliest time. It's not necessarily the best use of the tuple concept.
That seems kind of weird to me. Saying that in a Message passing system, only recipients get the message- that seems bogus to me. At least in a ComponentBus architecture, which broadcasts messages to anyone who's interested- Just like a TupleSpace!
Most messaging systems are such that each message has a sender and a recipient. Most messages go directly to one intended destination. Some message systems further allow destinations to be groups, so each member of the group gets a copy. Still other messaging systems allow broadcast so that everyone gets a copy.
Tuple Space is not like that. Tuples are put in the bag. Each process can then find a tuple that matches their search criteria and remove it from the bag. If you choose to have as a field in your tuple a destination process, and if selection is done on that field, then tuples can simulate message passing. By copying rather than removing tuples you can also simulate messages to groups, and broadcast messages.
Tuple Space lets you emulate all the possible versions of asynchronous message passing.
Broadcast messages are
not like
Tuple Space. A broadcast message is received by everyone whether they want it or not. Tuples are extracted or copied under the control of the reader/receiver.
One of the key differences between a
TupleSpace and a message queue involves the temporal aspect. Generally with a message queue once the message has reached the front of the queue and been processed it is gone. With a
TupleSpace that does not have to happen. A Tuple can be placed into the
TupleSpace and it may never be taken. Or it may be taken in a month. Or it might already have been taken by the time you read this sentence. The temporal aspect is a very powerful part of TupleSpaces
?.
But here's the question: is
TupleSpace a
TopologicalSpace ?
If it were a set of tuples rather than a bag, then it would be (a discrete topology). But I don't think there's anything particularly enlightening or helpful about that.
A question. On
TupleSpaceScalability, I just made the assertion that a distributed, persistent, transactional, fault tolerant
AssociativeMemory cannot scale linearly; that is,
TupleSpace won't work on the Internet, precisely because of its underlying "distributed shared memory" idea. Some assumptions have to be relaxed slightly; I've indicated one possible direction there, but there must be others. What do you think? -- VladimirSlepnev
?
Sounds like a singleton dataset, or a cached table, or a global linked list, or an abstraction of any of those. The add/remove/copy/search/etc features are all available in tables/SQL, so what is the distinguishing benefit of this other than it explicitly residing in memory?
A TupleSpace is arguably a more primitive construct than a SQL DBMS. A SQL DBMS could conceivably be built using a TupleSpace implementation as its storage layer. It would, however, be an awkward AbstractionInversion to create a TupleSpace using an SQL DBMS, especially in cases where TupleSpace functionality is needed without requiring other aspects of SQL or DBMSes.
See also TripleSpace
? paper, a
TupleSpace where the tuples are RDF triples
http://www.deri.ie/fileadmin/documents/DERI-TR-2004-05-31.pdf
See
MultiCaster,
AssociativeMemory,
GenerativeCommunication,
MultiParadigmDatabase
Tuple Space
EditText of this page
(last edited June 7, 2009)