DJ Greaves.               First Draft, November 2004.

A Global Passive Tuple Space as a Data Storage and Communications Substrate for Ubiquitous Computing

To enable communication between ubiquitous computing devices and to allow automated detection of undesirable feature interaction, this work suggests that ubiquitous devices should use Passive Tuple Space concepts to represent data. The companion pages make the separate suggestion that Pushlogic be used to represent code.

We envisage a global (ubiquitous) passive tuple space data store that is implemented over multiple devices of various complexity and in various detailed ways. We call this our data substrate. It can also be used for communications, using the concept of shared variables. We have implemented a version that runs on three different processing platforms (Unix, Bare PC and Molly H8S cards) and two different networks (Ethernet and CAN bus (CAN not working yet)).

Background

Distributed Databases

This work has elements in common with the organization, constraint and alarm systems for high-level databases, but here the target is expanded to cover low-level, wide-area and embedded systems. Unlike synchronous event languages, we do not implement expensive, atomic events or transactions; instead, partial operations can occasionally be visible and a conservative diffing system, akin to a PDA synchronization protocol, is being investigated for rollback under failure. The exact share of responsibility between application code and the tuple substrate is under study.

Associativity

Previous work on Tuple Spaces and distributed hash tables (DHTs) has emphasised their power of associative lookup - finding a datum stored under a key. In our model, the only associative power needed is to read the value of a named field from a given tuple. Since we do not enforce schemas and we allow dynamic extension to the tuple with new fields (new tag names), we do provide associativity. However, our work does not rely or build strongly on this aspect.

Active Tuples

Ambients and other systems of 'Active Tuple Space Computation' were defined as Turing-complete process algebras. However, our current interest is in Passive Tuples for embedded applications and our focus is where a large amount of loosely-coupled data sharing is required and the applications are relatively simple and dynamic. We are interested in:

  • programming for good behaviour under partial failure,
  • the trade offs between synchronous and asynchronous eventing/messaging,
  • practicality of ASCII string wire protocols,
  • practicality of ASCII string data structures within constrained RAM devices,
  • levels of embedding in HLLs,
  • using automated formal proofs to validate and constrain dynamic system evolution.

Our Aims

A major goal of this research is to understand the cost/benefit trade off accruing when applied to low-power devices. Certain solutions in this space, such as OSGi, may be too heavyweight for many applications. Certainly our own approach is expensive in use of RAM when compared with the 32K bytes or so available on the lowest-cost micro-controllers, and so we recognise that proxying of devices behind a gateway can never be fully avoided at the bottom end.

We have implemented our tuple substrate in some basic devices, such as an alarm clock and DVD player. We need to write up our conclusions on RAM use and general feasibility for low-cost and embedded devices. A current research student, Henry Robinson, is looking at the scalability of Passive Tuple Space in the wide area, e.g. using Xenoservers, to revist the vision where they are the data structure for the global, eternal, distributed system (i.e. The Matrix).

Local Links

  • Supressing Ubicomp Skirmishes PPT - A general presentation at the IEE, May 05.

  • Tuple Prims Overview - A draft specification for a Universal Computing Substrate.

  • Tuple Computation Design - Ideas behind Tuple Space Computation.

  • Embedded Tuple Core - An Embedded Tuple Space Engine.

  • Simple Pushlogic SPL - A Declarative Runtime for Tuple Space Computation.

  • Pushlogic Timer - A timer device normally available.

  • Pebbles CD/DVD Player - A CD/DVD player implemented using the Embedded Tuple Core and Pushlogic.

  • Global Ordering Note - Analysis of The Global Ordering Protocol.

  • Back to Vision Page.

    Summary of Terms Used

    Pushlogic is the temporary name for a style of bounded, error-resilient programming that operates on Tuples. In Pushlogic, no unbounded looping constructs are allowed, except where the loop passes through a device with known minimum delay, such as a timer. In Simple Pushlogic, no tuple creation, list operations or other dynamic storage allocation is allowed. Simple Pushlogic is suitable for implementing the embedded applications in many ubiquitous devices, with small fixed memories, such as a DVD player or burglar alarm. Dynamic storage is required for advanced applications, such as a TiVo PVR that builds up a directory data structure.

    Passive Tuple Space Computation is a style of imperative computing where all data is held in Tuples. Tuples may contain other tuples, and hence a tree structure arises that has features like in common with XML. However, every Tuple resides somewhere in a global address space and fields of tuples can change at any time owing to the action of various atomic and non-atomic updates. Unlike active Tuples, passive Tuples do not contain executing processes.

    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 over UDP. It is implemented as combination of small C kernel and a Pushlogic standard runtime library.

    CBG SPL is a portable interpreter for Simple Pushlogic. It is implemented as a combination of a small C kernel and some libraries.

    Pushlogic Timer. This timer is available as a device to be used by any Pushlogic program.

    Pebbles CD Players. A pair of network-connected CD players have been implemented with their embedded control software in Pushlogic using Tuple Space Computation for their data.

  • (C) 2004 DJ Greaves.