1. 27
  1. 8

    See also: Syndicated actors for conversational concurrency, which is in-between tuple-spaces and standard actor systems.

    1. 4

      Wow, that is fascinating. I just submitted it to lobste.rs (it was already posted, but four years ago.)

      From their comparison with tuple spaces:

      With Tuplespaces, state-passing is fundamental. But the way state moves around a tuplespace system causes problems for both fault-tolerance and eventual consistency. Lots of research on Tuplespaces has explored ways to repair these deficits.

      The same issue occurred to me: what happens when a process using a tuple-space fails? If it reads an input tuple, but crashes before it can write a result, anything waiting on that result is stuck. You can wrap something like a try/catch block around it, to ensure an error tuple gets written … but if it’s an actual OS process or a remote network node, how do you guarantee that runs?

      1. 3

        I believe you can structure your space (via the tuples you persist) to be fault-tolerant by usage of blocking reads. I’d also hesitate to say “this computation errored out” when you can just add more observers to the space: if one observer crashes, it shouldn’t stop the processing, which I think is the point.

        I think the fault tolerance concerns are orthogonal to the idea of a tuple space: you can engineer fault tolerance out of them, without having to burden the concept with more responsibilities.

    2. 6

      This feels like it’s in the neighborhood of dataflow programming (sorry, I don’t have a nice intro link handy). The biggest two differences I see are that the core records in dataflow are maps rather than tuples, and dataflow is oriented towards longer-lived jobs distributed across multiple jobs rather than multiple processes/threads with shared memory.

      1. 3

        It’s very much related to dataflow! Tagged datums moving through a static or dynamic network of “processors” pretty much equates to multiple listeners taking and giving back to the tuple space as needed. You can trivially encode a dataflow program as a tuple space program, and the “shape” of the program through producer/consumer semantics.

      2. 5

        Something is unclear if there is two tuples (a, b, x) and (a, b, y) what does (a, b, t?) returns?

        1. 4

          If I’m remembering correctly:

          It removes (and yields the value from) either one or the other tuple. There’s no requirement on the implementation for the choice to be deterministic at all.

          1. 3

            That’s correct. For all intents and purposes, the insertion order is undefined, but a lot of implementations allow you to specify an ordering.

            The nondeterministic approach is the most common, AFAIK, though.

        2. 3

          Aren’t tuples spaces implementable as just a relational database? Insert to put, delete to delete?

          1. 8

            The blocking behavior of take() is also important, and I’ve never seen that in a relational DB. As mentioned it’s more of a distribution and concurrency primitive than a data storage and querying primitive. I could imagine the query part approaching the power of SQL, but I don’t think any systems did so.

            1. 2

              Oh…now that’s an interesting feature.

              1. 2

                It’s good question though and makes me think that relational databases (and even sqlite) should support some blocking primitive.

                Although on second thought, I also don’t think you can’t SELECT + DELETE atomically, where the DELETE depends on the result of the SELECT? Like you would have a LIMIT 1 query and then want to both retrieve that one tuple, and delete it atomically.

                You might be able to simulate by retrying with exponential backoff on an empty query. Another thing you might want is a blocking PUT/INSERT to simulate the backpressure we were talking about on the other thread. Although the one system I worked with that resembled a tuple space didn’t have this.

                1. 3

                  In a database you’d SELECT first, then DELETE the row by its primary key, but wrap those in a transaction for atomicity.

                  But my preconception of tuple spaces is that a tuple often represents a small unit of work, like one computation, in which case a database transaction would add many orders of magnitude overhead.

                  1. 2

                    Well, Postgres extensions would allow you to return the value of a deleted row I believe. The blocking bit would be the magical bit, on both.

              2. 4

                Tuple Spaces are more about coordination and communication than data storage. It’s not just putting and deleting, it’s combinations of instructions and them being atomic.

                Matching and retrieving a tuple from the store, for example, deletes it so that no other process monitoring the tuple store can read it. It’s more akin to a different kind of message bus/queue than a relational database, and you’d face overhead if you implemented tuple spaces in terms of transactions on a table.

              3. 3

                Does anybody know an efficient or even production-ready implementation of this?

                1. 3

                  I have used Rinda, the Ruby implementation of Linda, once at work to avoid depending on an external message broker.

                  Basically, there was one server process that collected all messages sent by the computers on the network and a web service implemented in Rails that queried the tuple space. There was also the possibility to post messages to the tuple space that were essentially commands for certain computers to run.

                2. 3

                  The Wikipedia article has a pretty good overview, and many references to books and articles.

                  It says “implementations of tuple spaces have also been developed for Java (JavaSpaces), Lisp, Lua, Prolog, Python, Ruby, Smalltalk, Tcl, and the .NET Framework” but doesn’t actually name any other than Linda and JavaSpaces.

                  1. 2

                    One of my favorite implementations is rinda! https://github.com/ruby/rinda

                  2. 2

                    This actually sounds like something that can be implemented using software transactional memory, of which there are many implementations.

                    1. 2

                      This seems very much like one of the common ways to handle concurrent processing with Prolog; assertz/1 to put, retract/1 to take, maybe thread_wait/2 to block.

                      1. 1

                        Reminds me a lot of Clojure’s core.async. It’s a very cool idea.