Higher-Order Active Tuple Spaces (ATS)

This page has some ideas from last year which we have taken further now. Please see the other pages.

Most computing in the long-term future will be performed on top of a Universal or Ubiquitous Computing Substrate (UCS). This is the ultimate network PC. A number of predictions are that this substrate will consist of a global, eternal active tuple space (ATS).

This web page gives an outline of a typical system as currently envisaged. Please note that this is only one layer in the final application systems. This layer is pasted as universal jam between the Internet (or future evolution thereof) and major middleware functions, such as asynchronous eventing or synchronous RPC. The middleware functions will, in general, be far more strongly typed, but use localised or application-specific type schemas. The ATS layer is the only component with a global, eternal type schema and semantics.

Prior work on tuple spaces has emphasised the associative lookup facilities, but these are not emphasised here. Most lookup will be on the primary key (e.g. URI) and only rarely will associative lookup on arbitrary fields be required.

We first define primitive operations for the active tuple space (ATS) in terms of their operational semantics and then using a a number of applications as examples, we show how to use them in real-time, under simulated faster than real time execution and formal analysis.

ATS - Basic Design Decisions

A tuple space is a top-level universe consisting of named tuples. Each tuple may contain further tuples, implying heirarchic naming overall. Each tuple has a number of fields. XML is one possible representation. In an active tuple space (ATS), certain of the fields of a tuple may contain running software. The system is higher-order in that tuples can spawn further tuples.

There are a number of possible flavours of ATS within this definition. We make a number of basic design decisions to define our own flavour:

• Every tuple has associated credit and when its credit runs out, the tuple can be deleted by the substrate.

• Creating a new tuple costs according to the initial credit provided to the new tuple and the admin charges made by the hosting substrate entity.

• Every tuple has a unique name and address understood by the substrate. The substrate primitively supports redirection to automate the tracking of migrated tuples, but such operations inveitably cost more.

• There is no global type schema for tuple contents. Tuples must explicitly or implicitly refer to their own schema.

• The only datatypes are credit, date/time, tuple addresses/storage locations and ASCII strings. The aggregating or abstract datatype is the tuple itself. Consequently, all software in active tuples is represented as strings, which is essentially normal practice anyway.

• A tuple may only be accessed if its address is known. This gives security. Tuples may have multiple, different addresses to provide a capability system for restricted access to different operations or revokable capabilities to different clients. The substrate defines a restricted wildcard address resolution facility to provide associative look-up without compromising security.

• The primitive operations between active tuples and an active tuple and the substrate are listed below.

Primitive Tuple Operations

The substrate models an attractive force that causes tuples to encounter each other and can trigger method or function application. Under the biotic matrix model, this represents the behaviour of catalysts and enzymes. In addition, tuples can peform explicit operations on other tuples.

The Pi Calculus and the Ambient Calculus are process algebras of sufficient power to provide a useful ATS. However, the concepts of cost, power and expiry are not natively implemented. Also, these slightly older process calculi support rather abstract named and relative (respective) addressing modes for peer-to-peer communication. To make a practical ATS, we make various extensions and prescribe the addressing and powering aspects. (Addressing has to relate to the Internet and powering has to relate to money).

The internal operation of an active tuple is not a primary architectural issue: it can be coded in any programming language or style. Therefore, active tuples can vary in trustworthyness, from those that are transparent in their behaviour (e.g. using obvious or proof-carrying coding) to those that are opaque. Trust may also be widely interpreted with respect to an authenticated signatorary system, as in 'this code was signed at MS Redmond'. However, such trust is an overlay on the basic architecture with no special primitives.

The following primitives are suggested: read field/view/all, write field, execute method, clone, create, destroy, refinance.

Power Supply

A major aspect of an eternal, global ATS is who pays for it. Using the biotic matrix paradigm, we need to define and provide the heart, lungs, kidneys and so on. The system is powered through the provision of storage, network and process cycles.

In the fullness of time, all money and electronic funds transfer will probably be handled within the ATS, but perhaps with a residual level of shipping gold bars between corporations. But in the short term, we will continue to see all large electronic fund transactions being carried out by our current banking techniques and various systems for turning such `hard cash' into credit to power the tuple space. The funding of the mobile phone system by top-up of smart cards is a seeding scenario, although currently, electronic cash is not widely transfered between handsets etc..

Credit drain is through the substrate into the pockets of the substrate providers (SPs). This is very natural. All decisions to spend credit will ultimately originate from human actions, since no sane person ever authorises anything that has an unlimited cost liability. Therefore, energy supply in the form of credit injection will occur at any time a person requires a service, perhaps paid in advance. For instance, to send an email, an electronic stamp is required. (This wipes out spammers too, so is a very good idea!). This stamp can be a tuple. Equally, a whole financial service, such as an insurance company, can be a tuple.

There are two essential forms of electronic credit: both are suitable for use. The first is a hard currency which can be exchanged for real money at various places, whereas the second is a deterrent coinage, which can be minted by servers that wish not to be subject to denial of service attacks through excessive traffic. An example form of deterrent currency is the `recognise characters' test implemented by certain web search engines, but a more suitable version of this for peer-to-peer computing is simply to issue credit in return for prime factorisation.

Address Format

Most active objects will refer to each other using local, dynamic or relative addressing, but Internet/WWW style URIs will also be needed.

The Internet provides a valuable and almost inveitable infrastructure for the global ATS. Therefore, absolute addresses will be built largely on Internet URIs. However, intelligent, active, policy-driven NAT is bound to have big consequence. Address translation and directory services will eventually become the most strategic and important services, where new policies and schemes can be applied to modify the behaviour of older applications.

Advanced Reservation and Provisioning

An essential aspect of any system is availability. People will spend money to have the required levels of service available at short notice (e.g. I own a car and drive less than 500 miles a year). As well as private ownership, the equivalent of today's networking VPN as an active object substrate will therefore evolve: it has the advantage of easy management. In principle, provision and reservation systems will provide a less brutal mechanism for this, but its hard to say when they might be successful.

Current Status

These ideas were written as a strawman middleware for the Pebbles project, although currently the main project is using XML RPC directly at the API without the active object layer. The ideas are now being developed separately as shown on the accompanying web pages.