Lecture Notes for Concurrent Programming

12 August 2003 - Tuple Spaces

Outline

• Asynchrony in space and names.

• Tuple spaces.

  • Tuples and tuple-space operations.

  • Writing the tuple space.

• Tuple-space programming.

  • Node-pairing code.

• JavaSpace

  • The JavaSpace interface.

  • Notification

  • Transactions

Time, Space, and Names

• Concurrent computations are asynchronous in time.

  • Execution rates are not coordinated.

  • Coordinating time makes concurrent programming hard.

• What about location? Are concurrent computations asynchronous in space?

  • Not really; coordination implies an agreement in location.

    • Lock this mutex to access this critical section.

    • Send this message there.

• Are concurrent computations asynchronous in names?

  • It depends.

    • Shared-memory doesn't have names, so there's nothing to coordinate.

    • Message passing has names; the sender and receiver must know each other.

  • But remember the shared-memory message-passing duality.

Asynchrony in Space and Names

• Is asynchrony in space or names valuable?

  • More asynchrony means less coordination and overhead.

    • Computations don't pay for services they don't use.

  • However, required synchronization may become more expensive.

    • Hand-crafted synchronization takes time and effort.

    • It may or may not be more efficient than system synchronization.

• Compare C.B. radio to cell phones.

  • Both are asynchronous in space (roughly).

  • C.B.s are asynchronous in names, cell phones are not.

• Compare C.B. radio to cell phones.

  • Both are asynchronous in space (roughly).

  • C.B.s are asynchronous in names, cell phones are not.

Tuple Spaces

• Is there a C.B. radio for concurrent computations?

  • That supports easy and cheap synchronization over names and locations if needed.

• David Gelernter answered this question in the early 1980s.

  • Generative Communications in Linda by David Gelernter, ACM Transactions on Programming Languages and Systems, January, 1985.

• Gelernter defined a distributed, content-addressable memory called a tuple space.

  • "Distributed" means location asynchronous.

  • "Content-addressable" means name asynchronous.

    • Access to data is based on data values.

• A tuple space gives concurrent computations asynchrony on all three dimensions.

  • The computations then work out coordination as needed.

• Gelernter named his first tuple-space system Linda.

Tuples

• A data tuple (or just tuple) is a sequence of 1 or more values.

  • (c0, c1, ...)

  • Zero-value tuples might make sense too.

  • Each tuple value is called a coordinate.

• Two tuples match if

  1. The two tuples have the same number of coordinates.

  2. The types of the ith coordinates match.

  3. The values of the ith coordinates are the same.

  • The tuple ("hello", 1.0) doesn't match
    the tuple (1, "hello").

  • The tuple ("good-bye", 1.0) doesn't match
    the tuple ("hello", 1.0).

Tuple-Space Operations

• The tuple-space operations put (write) and get (read) a tuple.

  • Each operation has in various forms.

• get(c0, c1, ...) gets a matching tuple from the tuple space.

  • The corresponding tuple coordinate must match the value c_i.

  • If c_i is ?variable, the corresponding tuple coordinate is assigned to variable.

  • If several tuples match, any one is returned.

• get() blocks until a matching tuple is available.

  • try_get() returns false if no tuple matches.

• get() removes the matching tuple from the tuple space.

  • look() matches and doesn't remove a tuple.

  • try_look() is nonblocking.

Writing the Tuple Space

• put(c0, c1, ...) adds a tuple with the given coordinates to the tuple space.

  • The tuple space maintains copies of the same tuple.

• eval(c0, c1, ...) adds a process tuple to the tuple space.

  • A thread evaluates each coordinate in turn.

  • When all coordinates are evaluated, the process tuple turns into a data tuple.

    • And the thread exits.

  • This is how tuple spaces add concurrency to sequential languages.

• Tuple-space operations are atomic.

  • eval() doesn't reveal intermediate tuple states.

  • There's no fighting over tuple matching.

Tuple-Space Programming

• Tuple-space programming is based on asynchronous message passing.

  • Each tuple corresponds to a message.

  • Each message tuple usually contains a tag value to identify itself to the receiver.

    • The tag also avoids conflicts with existing messages.

• Example - graph node pairing.

  ("partner?", receiverIndex, senderIndex)
  
  ("accepted", receiverIndex, senderIndex)
  
  ("declined", receiverIndex, senderIndex)
  

  • The first coordinate is the message type.

  • The second coordinate is the receiver.

  • The third coordinate is the sender.

  • It's up to the constituent computations to define the protocol.

Node-Pairing Code

• Order nodes to avoid deadlock.

  • Receive requests from nodes with higher indices.

    • Accept the first one that arrives.

  • Make requests to nodes with lower indices.

  while neighbors != { }
    get(msg, nodeIndex, senderIndex)
    neighbors.remove(senderIndex)
  
    if msg == "partner?"
      assert senderIndex > nodeIndex
      partnerIndex = senderIndex
      put("accepted", senderIndex, nodeIndex)
      break
  
    assert msg == "declined"
    assert senderIndex < nodeIndex
  

• Anticipate offers from other higher-indexed neighbors and pre-emptively decline them.

  foreach nbr in neighbors
    if nbr.nodeIndex > nodeIndex
      put("declined", nbr.nodeIndex, nodeIndex)
      neighbors.remove(nbr)
  

Node-Pairing Code (Continued)

• If this node is still unpaired, ask the lower-indexed neighbors to pair up.

  if partnerIndex == nodeIndex
  
    foreach nbr in neighbors
  
      assert nbr.nodeIndex < nodeIndex
  
      put("partner?", nbr.nodeIndex, nodeIndex)
      get(msg, nodeIndex, nbr.nodeIndex)
  
      if (msg == "accepted")
        partnerIndex = nbr.nodeIndex
        break
  
      assert msg == "declined"
  

Status

• Tuple spaces evolved into a coordination language for adding concurrency to sequential languages.

  • Linda in Context by Nick Carriero and David Gelernter, Communications of the ACM, April 1989.

• Academics have added tuple spaces to various languages.

  • Prolog, Lisp, and the usual suspects.

• Tuple spaces have undergone various extensions.

  • Multiple tuple spaces, re-introducing location synchrony.

  • Persistence, extending time asynchrony.

  • Other tuple-space operations (matching-tuple signals).

• Commercially, tuple spaces have been influential but not successful.

  • Building scalable, efficient tuple spaces is hard.

JavaSpace

• JavaSpace is an implementation of tuple spaces in Java.

  • Built on top of Jini, and offered as a Jini service.

• JavaSpace Terminology differs from Gelernter's; I'll stick to the Gelernter's terminology.

• JavaSpace is available for downloading from Sun.

  • Unfortunately, it seems you need all of Jini

JavaSpace Objectives

• Exploit tuple spaces in distributed systems.

  • Allowing simple design and implementation.

• Minimal client requirements.

  • The network is the computer, remember.

• A multiplicity of possible JavaSpace implementations co-existing.

  • Implementation agnostic.

• Improve reliability with replication and redundancy.

  • But things start to get not so easy.

JavaSpace Features

• There can be several tuple spaces.

  • And Java clients can access subsets of them.

• The Jini concept of leases are extended to tuples.

  • A clever form of garbage collection.

• Tuples and their coordinates are class instances.

  • Tuple matching includes the subtype relation.

  • Class instances cannot be called while in a JavaSpace.

• Tuple-space interactions can be arranged as transactions.

  • This is the most significant feature of JavaSpace.

JavaSpace Tuples

• A JavaSpace tuple is an class that implements the Entry interface.

  public class Message
  implements Entry
    public String content
    public Message() { }
  

• Otherwise, it's just like a normal class.

  message msg = new Message()
  msg.content = "Hello world!"
  

• Tuple field types must be classes.

  • Basic types have to be boxed into classes (e.g. Integer)

• Coordinates are de-activated when the tuple is in a space.

  • Can't call methods, can't access fields

The JavaSpace Interface

• A JavaSpace is any class that (correctly) implements the JavaSpace interface.

  package net.jini.spaces
  
  public interface JavaSpace
  
    EventRegistration notify(
      Entry tmpl, Transaction txn, 
      RemoteEventListener listener,
      long lease, MarshalledObject handback) 
  
    Entry read(
      Entry tmpl, Transaction txn, long timeout) 
  
    Entry readIfExists(
      Entry tmpl, Transaction txn, long timeout) 
  
    Entry take(
      Entry tmpl, Transaction txn, long timeout) 
  
    Entry takeIfExists(
      Entry tmpl, Transaction txn, long timeout) 
  
    Lease write(
      Entry entry, Transaction txn, long lease) 
  
    // There are others.
  

JavaSpace Writing

• A write into a JavaSpace copies the tuple into the space.

  JavaSpace space = SpaceAccessor.getSpace()
  
  space.write(       // to this space
    msg,             // write this tuple
    null,            // in no transaction
    Lease.FOREVER)   // to last forever
  

• Multiple writes on the same tuple create multiple copies of the tuple in the JavaSpace.

• The write returns a lease for the tuple written.

  • The writer can control the tuple life-time in the tuple space through the lease.

• Any suitable external protocol can be used to find JavaSpaces.

  • Jini look-up services mainly, but there can be others.

JavaSpace Reading

• Taking removes a tuple, reading does not.

• Null tuple coordinates cause a match.

  • Subtype matching is supported.

• Candidate selection is nondeterministic.

  • Repeated, identical reads may return different tuples each time.

• Taking a tuple may throw exceptions.

  • Exceptions indicate, among other things, coordinate marshaling errors, communication errors, or transaction errors.

• Example

  Message result =     // Into this tuple
    (Message)	     // a message
    space.read(        // read from this space
      new Message(),   // with any content
      null,            // under no transaction
      Long.MAX_VALUE)  // wait this long
  

  • Read time-outs return null.

Notification

• Watch for specific tuples appearing in a tuple space.

  • Like delegating a read to a subordinate thread.

• Example

  EventRegistration watcher = 
    notify(
      tpl,        // look for this tuple
      txn,        // as part of this transaction
      listener,   // calling this listener
      lease,      // until this expires
      handback)   // passing this to the listener
  

  • Notification matching is the same as read matching.

Transactions

• Putting operations in a transaction is equivalent to making them atomic.

  • The transaction either succeeds or fails; there are no intermediate states.

  • The transaction manager is responsible for undoing intermediate results

• The Jini transaction service (Mahalo) is a significant feature to have in a distributed system.

  • Designing transaction support from scratch is a hard job.

  • It is unclear to me how effective or restrictive Mahalo is in practice.

Points to Remember

• Asynchrony is easy to use but hard to think about.

  • Unless you need synchrony, then it may be hard to use too.

• A tuple space is a distributed, associative memory.

  • Remember that phrase and impress your friends.

• Tuple-space programming is similar to asynchronous message passing.

  • But the receivers are anonymous and location independent.

• JavaSpace is an implementation of a tuple-space distributed infrastructure.

  • Will there be any others?

This page last modified on 12 August 2003.