LinuxTuples

Here is some Doxygen documentation for this code. To get the tarball, visit the Project Page and look for "Download". I've been doing a pretty good job of keeping the README up-to-date.

LinuxTuples is an open-source tuple space server, with associated code for writing clients, designed to run on a networked cluster of Linux/Intel boxes. The tuple space is maintained on one machine on the the network.

Tuples offer a convenient and intuitive way to write parallel programs. A tuple space represents a shared communication channel allowing processes anywhere on the network to communicate with one another.

A tuple space is a database of ordered lists of typed values. For instance, the tuple (2, 5.439, "abc") is made of an integer, a float, and a string.

A tuple space functions like a community bulletin board. Anybody can post a message, or take a message away, or read a message and leave it for others to read. If somebody is waiting for a particular message and doesn t find it immediately, he can go do something else, or wait to see if the message arrives. If nobody removes a message, it will remain on the bulletin board indefinitely.

The meaning of a tuple's elements is a convention agreed upon by the client programs. Tuples will often represent requests for computations or the results of computations. They can also represent public knowledge shared by all the programs in the entire system, such as the values of physical constants, or the trading prices of commodities.

LinuxTuples is written in C, with a client API for Python. It should be fairly easy to write client APIs for other languages, as long as they have a representation for ordered lists of different-typed values.

History

In the 1980s, David Gelernter of Yale University had a very clever idea about coordinating parallel computations, which he described in his book Mirror Worlds (ISBN 019507906X). At that time, the two preferred approaches to parallel computing interprocess communication were shared memory (expensive, requires custom hardware) and message-passing.

Gelernter's insights were (1) that messages can be anonymous -- they often don t need to be addressed to a specific recipient, and the recipient often doesn t need to know who sent the message, and (2) that they should persist if not immediately picked up. He formalized his insights with the invention of a tuple space , which has since been adopted in the Java world as Javaspaces.

Tuple operations

There is a short list of legal interactions that a client can have with the tuple space. (Where tuple space literature normally vavors "in" and "out", I have chosen to use "put" and "get" to avoid a conflict with the Python "in" keyword.)

PUT - The client constructs a tuple and puts it into the tuple space.
GET - The client constructs a template to match a subset of tuples, using wildcards for some fields, and removes the first tuple from the tuple space that matches the template. If no matching tuple can be found, the client is blocked until a match exists.
READ - Like GET, the client builds a template and waits for a matching tuple, but takes a copy, leaving the tuple in the tuple space.
GET_NB - A non-blocking version of GET; in the event that a matching tuple is not found, a NULL pointer is returned instead.
READ_NB - A non-blocking version of READ.

There are a few additional operations that are really conveniences more than fundamental pieces of the system.

DUMP - Get a list of the tuples currently in the space. Optionally, get a list of only those tuples that match at least one of a set of templates.
LOG - The client receives a continuous log of what the tuple server is doing.

Templates and wildcards

A template is used for a GET or READ operation, to put wildcards in some fields. Doing this in C is easy. We specify the form of a tuple or template using a printf-like format string, and then fill in the fields that need values.

    struct tuple *s, *t;
    s = make_tuple("sid???", "will work for electrons", 1234, 2.71828);
    t = get_tuple(s);

Python's tuples are naturally mapped to LinuxTuples tuples, using None as a wildcard.

    import linuxtuples
    conn = linuxtuples.connect()
    t = conn.get( ("will work for electrons", 1234, 2.71828, None, None, None) )