DJ Greaves.               First Draft, November 2004. Up To Parent Page.

CBG Embedded Tuple Core.

Part of An Embedded Platform for Push Logic and Tuple Space Computing

Abstract

CBG Embedded Tuple Core is a runtime system for Tuple Space computation designed for embedded applications. It uses URIs for remote tuple names and defines its own federation protocol, called ETC, that operates over UDP. It is implemented as combination of small C kernel and a Push Logic standard runtime library.

Overview

Embedded Tuple Core maintains an in-store data structure for holding Tuples and implements a federation protocol over UDP that allows interaction with peer Tuple Cores running on devices. One attraction of Tuple Computation is that many possible implementations of the core services are possible, ranging from a monolithic server to a distributed hash table.

All data is held as tuples. A tuple has a primary key field and a number of fields. Each field is named with a tag that is a string. The primary key tag name is always "$PK". Each field has a value that is one of the following:

  • A string,
  • A credit,
  • A time/date,
  • A URI,
  • A tuple.

The value field of the primary key is always a URI.

Although a tuple may contain further tuples, and be included in several value fields, recursive structures are not allowed and hence all tuples in the core are part of a partial ordering, with one or more tuples sitting at a top-level.

As well as a primary key, every tuple has $credit and $lifetime attributes, although these are calculated by Tuple Core when needed, rather than being stored in each tuple. The lifetime is the time before the tuple is deleted by Tuple Core in microseconds. The credit is related to the time by a charging rate applied at the instance of Tuple Core that is hosting the Tuple. The $refcount field is supported for read access using various internal mechanisms.

Only a restricted set of characters is allowed in tag names. Specifically, dollars and those such as dot and slash that are used to form path names must not occur.

The use of slash, equals and colon in any string has efficiency significance. The Tuple Core can internally split all strings at slashes, equals signs and colons and stores the components separately. This tends to save memory where these characters are used in patterns or as a standard form association list but can waste memory if the characters occur randomly in strings. The core internally stores short base ten digit strings using a binary representation, but these are not differentiable from strings over the API.

Any data stored under the special tag $RO will be returned via a read-only handle that cannot be used for future SetValue operations.

Initialisation and Local Root Tuple

When Tuple Core is started, certain system Tuples are inserted in the Core, but it is otherwise empty. Generally, the device hosting Tuple Core will host other devices as well, and these devices then register themselves in the Core by inserting their own Tuples.

Several system devices will also commonly be registered in the Core are a network interface, supporting UDP, a serial console debug port, a timer and a Push Logic interpreter. The Push Logic interpreter will register further tuples relating to libraries.

A local root tuple exists in every running instance of a Tuple Core. Its name is "$" and a number of pre-defined fields are always present. The TUPS field is access with "$#TUPS" and is a root tuple that contains all locally held tuples, stored using their primary key as tag names. One might think that the root should only contain the outer-most member of any nested tuple tree, but owing to the naming structure used, this is intrinsic. Another field present in the local root tuple is "$#$ME" which is the leading part of a URI that can be prefixed to any tuple held below the root to give its unique global address.

The Core may be accessed by the local host using a C library API. It is accessed over the network using the ETC protocol. The C API is for low-level imperative programming only. It is intended that all application code is written declaratively in Push Logic or similar. A use of the C API would be in a simple device driver for a keypad, that needs to update the values of the fields modelling the keypad as each key is pressed or released. The API allows a non-blocking upcall to be registered per tuple that is called whenever any field in that tuple is updated.

Local API Primitive Operations

The main components of the imperative API are:

enum tc_t { tc_string, tc_uri, tc_credit, tc_datetime, tc_tup, tc_int };

tc_Initialise();

tc_Refresh(TUP *handle, int credit);

tc_SetValue(TUP *handle, TUP *tag, TUP *value);

tc_GetValue(TUP *handle, TUP *tag);

tc_ListTags(TUP *handle);

tc_StrToTup(char *s, tc_t t);

tc_TupToStr(TUP *handle);

tc_Upcall(TUP *handle, (*f)(TUP *field, TUP *value));

The vstore and tread primitives are not supported in the current version.

Certain tuple handles are constant error values: TUP_WRITE_PROTECTED, TUP_NOSUCHFIELD, TUP_NOSUCHTUP, TUP_NETWORKTIMEOUT.

ETC Federation Protocol

The Embedded Tuple Core operates a protocol over the network called ETC. This protocol enables tuples hosted on a given instance of Tuple Core to be logically contained in tuples hosted on a peer. It provides access functions and also the soft state refresh operations required for distributed garbage collection. Future versions could support transparent migration of tuples between hosts.

When a GetValue call returns a field that is a Tuple Core URI, this is visible in standard URI syntax when viewed with TupToStr, but is remotely accessed over the network when used as a handle for subsequent calls.

Devices and services that wish to access the tuple space are not prohibited from directly using the ETC protocol, but it is expected that most devices and services will use the C API on their local instance of Tuple Core that will in turn generate and process ETC messages on their behalf.

Both Tuples and Push Logic rules have ordering constraints. Tuples may not be contained in other tuples that in turn contain themselves. A Push Logic rule may not modify fields that in turn might trigger rules that might trigger that rule. Both these orderings span the global tuple space. A natural number called level is associated with every rule and tuple so that these ordering constraints are easily checked. This does not lead to a large memory overhead, because many of the levels can be stored implicitly in core data structures. The level associated with any tuple can be viewed for debugging purposes as a string by reading the "#$LEV" field of the tuple. The control of levels is an interesting topic to be covered in a separate note "A Global Ad Hoc Level Protocol".

(C) 2004 DJ Greaves.