Grid Computing & the Linda Programming Model

(via Phil Windley)

This Dr. Dobbs article describes how tuplespaces can serve as an alternative to web-service message passing APIs.

A nice explantion of the Linda programming model.

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Yet another impedance mismatch?

I expect the original Linda primitives to work best in the languages with extremely lightweight concurrency (so long "who needs 106 threads anyway"). In Java one cannot afford to block on "in()", so JavaSpaces adopted notifications, which in my opinion killed the conceptual simplicity. All in all, I tend to perceive Linda as a precursor of Oz programming model :)

Monitoring tuples

In the area of asynchronous tuple space access, I find the work of Antony Rowstron and collaborators very interesting. They are using a new primitive called monitor which is basically equivalent to an initial iteration of the query result set, plus a subsequent observation of changes to the set. (i.e. all tuples currently in the set are sent, and all that get added in the future, until a deregistration is performed.)

Section 2 of the paper State- and Event-based Reactive Programming in Shared Dataspaces gives a short example of how to program with monitor a buddy list application, for tracking the dynamically changing status of other users.

They also critique the JavaSpaces notify, which only sends future tuples, but not those currently in the set, which shifts the burden on the application programmer.

The Pi Calculus?

This discussion has me wondering whether there are any serious programming-language efforts based on process algebras such as the Pi Calculus (see book by Davide Sangiorgi & David Walker, and Robin Milner's "Communicating and Mobile Processes"). It would be interesting to know of research efforts as well as any industrial efforts (the latter would be admittedly adventurous :)

Linda is lovely but getting long in the tooth, and I don't know enough about JavaSpaces to support my suspicion that it might be a little ad-hoc.

Brian Beckman
http://weblogs.asp.net/brianbec

Re: The Pi Calculus

Brian Beckman: This discussion has me wondering whether there are any serious programming-language efforts based on process algebras such as the Pi Calculus (see book by Davide Sangiorgi & David Walker, and Robin Milner's "Communicating and Mobile Processes"). It would be interesting to know of research efforts as well as any industrial efforts (the latter would be admittedly adventurous :)

Perhaps the most interesting at the moment is described in PiLib: A Hosted Language for Pi-Calculus Style Concurrency, which describes how the Pi Calculus can be embedded in Scala, which runs atop either the JVM or the CLR. This is far and away the most practical Pi Calculus implementation I've seen yet.

Of course, the canonical example of a Pi-Calculus language is Pierce's Pict. I've never investigated it, personally.

Nomadic Pict apparently extends the Pi Calculus to deal with distribution issues.

Nomadic Pict leads to Peter Sewell leads to Acute: high-level programming language design for distributed computation, which covers a lot of distributed language design turf in a way that relies on very few language primitives and leaves most of the work to the library level, but still manages to deal with issues like dynamic linking and rebinding of modules to local resources, type-safe network interaction, concurrency, mobility, security... a raft of good stuff. In fact, if you hop up a couple of levels to Sewell's home page, you see that he's been doing amazing stuff for years.

How is a tuple-space better than a database?

Publishing a tuple seems a lot like inserting a row into a table in a relational database, while the 'take' operation is a select followed by a delete (a bit more awkward though).

It's unclear to me how communicating via a tuple space is any better than using a database. For example, the Blitz implementation of JavaSpaces is apparently implemented on top of Berkeley DB, so it's no more fault-tolerant than MySQL. And SQL allows more flexible queries.

Tuple-space vs SQL database

A tuple-space has a crucial property: the client can be notified about changes made to data, which is done by registering a listener or by blocking to read a specific tuple. No active waiting! This is hardly possible in the SQL alone.

Easily done with a database trigger

The most popular databases implement so-called "triggers". A trigger can perform any of a wide variety of actions should a tuple change.

Triggers are NOT part of the relational database specification or model but merely a common and useful feature.

Maybe you could implement a tuple space on top of a DBMS

In my attempt at an implementation, each client passes a callback function along with a template to the tuple selector. The client process will block until this callback is called.

If the selector finds a tuple, it calls the callback immediately. If a tuple isn't found, the template and callback function are added to a queue of unfulfilled requests. Whenever a new tuple is added, we try to match it up with a request in the queue and call the request's callback with the new tuple. If the request was non-destructive, we can then go on and try to match with any other pending requests.

If a DB product supports sending notifications to clients, then this behaviour could conceivably be implemented using triggers (or during a stored procedure used to add the new tuple). Otherwise I guess each client could poll continuously for some notification message - I've seen this done on SQL Server in an "enterprise" setting...

C-omega sort of has tuple spaces

It seems like in C-omega's concurrency model, each object could be considered a single-process, in-memory tuple space. When you call an asynchronous method, it adds the method arguments as a tuple to the object's event queue. The biggest difference I see is that matching in C-omega happens on the method name and argument types, not on the data.

Investigating in Python

I've started on a simple tuple space implementation in Python (supports only in, rd and out), chiefly in order to have something to play around with.

In case anyone's curious, details and code can be found here, here and here.