LighTS: A Lightweight, Customizable Tuple Space Supporting Context-Aware Applications
Picco, and Dip. di Elettronica e Informazione, Politecnico di Milano, Italy {picco, balzarot,
The tuple space model inspired by Linda has recently been rediscovered by distributed middleware. Moreover, some re- searchers also applied it in the challenging scenarios involv- ing mobility and more specifically context-aware computing. Context information can be stored in the tuple space, and queried like any other data.
Nevertheless, it turns out that conventional tuple space implementations fall short of expectations in this new do- main. On one hand, many of the available systems provide a wealth of features, which make the resulting implementa- tion unnecessarily bloated and incompatible with the tight resource constraints typical of this field. Moreover, the tra- ditional Linda matching semantics based on value equal- ity are not appropriate for context-aware computing, where queries are often formulated over value ranges, and where there is a prominent need to deal with imprecise informa- tion coming from multiple sources.
Copyright By PowCoder代写 加微信 powcoder
In this paper, we describe a new tuple space implementa- tion called LighTS. Originally developed as the tuple space core of the Lime [11] system, LighTS provides an extensi- ble framework that makes it easy to introduce extensions to the tuple space, and in general customize the tuple space implementation. The design and programming interface of LighTS is presented, and its flexibility demonstrated by il- lustrating extensions that proved useful in the development of context-aware applications.
1. INTRODUCTION
The tuple space model inspired by Linda [8] has recently been rediscovered by distributed middleware. Commercial systems (e.g., TSpaces [1], JavaSpaces [2], GigaSpaces [3]) as well as academic ones (e.g., MARS [6], TuCSoN [13], Klaim [12], Lime [11]) are currently available.
Among these, the Lime system is particularly interesting, in that it adapts and extends Linda towards mobility, by transforming its global and persistent tuple space into one
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee.
SAC’05, March 13-17, 2005, Santa Fe, , USA. Copyright 2005 ACM 1-58113-964-0/05/0003 …$5.00.
that is federated and transiently shared according to con- nectivity. Moreover, this system has recently been used to develop context-aware applications.
In [10], the authors describe a simple location-aware appli- cation supporting collaborative exploration of geographical areas, e.g., to coordinate the help in a disaster recovery sce- nario. Users are equipped with portable computing devices and a localization system (e.g., GPS), are freely mobile, and are transiently connected through ad hoc wireless links. The key functionality provided is the ability for a user to request the displaying of the current location and/or trajectory of any other user, provided wireless connectivity is available towards her. The application is implemented by exploiting tuple spaces as repositories for context information—i.e., lo- cation data. The primitives of Lime are then used to seam- lessly perform queries not only on a local tuple space, but on all the spaces in range. For instance, the location of a user can be determined by performing a read operation for the location tuple associated to the given user identifier. The “lesson learned” distilled from this work is simple and yet relevant: tuple spaces can be successfully exploited to store not only the application data needed for coordination, but also data representing the physical context. The advantage is the provision of a single, unified programming interface—the coordination primitives—for accessing both forms of data, therefore simplifying the programmer’s chore.
Nevertheless, as the authors discuss in their findings, it turns out that the traditional matching semantics of Linda, based on comparing the exact values of tuple fields, is insuf- ficient for the needs of context-aware applications. Indeed, context-aware queries rarely revolve around exact values. For instance, in a sensor monitoring application, it may be required to find the identifiers of all the temperature sensors registering a value between 20 and 25 degrees. Or, in the application of [10] it may be needed to find the users within 500m, or those within r meters from the point (x, y). Often, even these queries are too precise, in that the user may have enough information only to formulate requests as informal as “find the sensors recording a hot temperature”, or “find the users close to me”. These needs sometimes surface also in conventional applications, but they are definitely exacer- bated in context-aware ones.
In this paper, we set out to close the gap between the tuple space model and context-aware applications, by ex- tending LighTS, the tuple space engine at the core of the Lime system. In contrast with available tuple space sys- tems, LighTS [4] was designed to be extremely lightweight and minimal, by providing a local tuple space with support
only for the basic Linda operations. Indeed, distribution, event notification, transactions—features typically provided by other systems—are built on top of LighTS by Lime. Nevertheless, the lack of sophisticated features is compen- sated by a design that renders LighTS highly customiz- able and extensible. In essence, the tuple space abstrac- tion provided by LighTS was conceived as a framework (in the object-oriented sense) rather than a closed system. The built-in instantiation of such framework provides the tradi- tional Linda abstractions, similarly to many other systems. At the same time, however, the modularity and encapsula- tion provided by its object-oriented design leaves room for customization, empowering the programmer with the ability to easily change performance aspects (e.g., changing the tu- ple space engine) or semantics features (e.g., redefine match- ing rules or add new features). This flexibility and extensi- bility, together its small footprint and simple design, are the defining features of LighTS.
We put forth two contributions. First, we present the overall architecture and programming interface of LighTS, and describe the mechanisms supporting customization and extension. Second, we show how these mechanisms can be exploited straightforwardly to suit the needs of context- aware applications. In particular, we describe the design of two additional matching semantics (one based on compari- son over value ranges and one based on fuzzy logic), and of a new feature which enables data aggregation at the tuple level. Finally, the ability to change the back-end of the im- plementation enables us to provide different deployment al- ternatives, including support for devices running Java2 Mi- cro Edition (J2ME).
The paper is organized as follows. Section 2 is a concise overview of Linda. Section 3 presents the overall design of LighTS, and shows how the resulting framework can be easily extended both in terms of performance and semantics. Section 4 discusses the extensions we introduced to better suit the requirements posed by context-aware applications. Section 5 briefly reports about implementation details and availability of the software package. Finally, Section 6 ends the paper with brief concluding remarks.
the tuple space the process performing the operation is sus- pended until a matching tuple becomes available. A typical extension to this synchronous model is the provision of a pair of asynchronous primitives inp and rdp, called probes, that allow non-blocking access to the tuple space. Moreover, some variants of Linda (e.g., [14]) provide also bulk opera- tions, which can be used to retrieve all matching tuples in one step1 .
LINDA IN A NUTSHELL
In this section we present the core features of LighTS, followed by the mechanisms for customizing and extending the framework, which are exploited in Section 4 to build new features useful for context-aware applications.
3.1 The Core API of LighTS
The core of LighTS is contained in the lights package and is constituted by a set of interfaces that model the fun- damental concepts of Linda (i.e., tuple spaces, tuples, and fields) and by a built-in implementation of these interfaces.
Tuple spaces. Figure 1 shows2 the interface ITupleSpace, which must be implemented by every tuple space object. The interface contains the basic Linda operations described in Section 2, i.e., insertion (out), blocking queries (in, rd), probes (inp, rdp), and bulk operations (outg, ing, rdg). Tu- ple spaces are expected to be created with a name, enabling an application to manage multiple tuple spaces, as suggested in [7]. The name of a tuple space can be retrieved through the method getName. Finally, ITupleSpace provides also a method count that returns the number of tuples currently in the tuple space.
Being an interface, ITupleSpace specifies only a syntac- tic contract between the implementor and the user of the implementing object, and nothing can be said about the semantics of the actual implementation. Therefore, for in- stance it is not possible to prescribe that accesses to the tuple space must be mutually exclusive, as usually required by Linda. This is an intrinsic limitation in expressivenes of the Java language (and other object-oriented approaches). Nevertheless, the built-in TupleSpace class, which imple- ments ITupleSpace, behaves like a traditional Linda tuple space by preserving atomicity of operations. Moreover, tu- ple insertion is performed by introducing in the tuple space a copy of the tuple parameter, to prevent side effects through aliasing. Since tuples may contain complex objects, copying relies on the semantics of Java serialization, which already deals with aliases inside object graphs. Upon insertion, a deep copy of the tuple parameter is obtained through seri- alization and immediate deserialization. A similar process is performed when a non-destructive read operation (rd, rdp, or rdg) is performed. Nevertheless, our TupleSpace imple- mentation can be configured to reduce the impact of serial- ization and trade space for speed, by storing a copy of the byte array containing the serialized tuple together with the tuple itself. This way, read operations are faster since they need to perform only a deserialization step to return their re- sult. The desired configuration is specified at creation time
1Linda implementations often include also an eval opera- tion which provides dynamic process creation and enables deferred evaluation of tuple fields. For the purposes of this work, however, we do not consider this operation further. 2Exceptions are omitted for the sake of readability.
In Linda, processes communicate through a shared tuple space that acts as a repository of elementary data structures, or tuples. A tuple space is a multiset of tuples that can be accessed concurrently by several processes. Each tuple is a sequence of typed fields, as in ⟨“foo”, 9, 27.5⟩, containing the information being communicated.
Tuples are added to a tuple space by performing an out(t) operation, and can be removed by executing in(p). Tuples are anonymous, thus their selection takes place through pat- tern matching on the tuple content. The argument p is often called a template or pattern, and its fields contain either actuals or formals. Actuals are values; the fields of the previous tuple are all actuals, while the last two fields of ⟨“foo”, ?integer, ?float⟩ are formals. Formals act like “wild cards”, and are matched against actuals when select- ing a tuple from the tuple space. For instance, the template above matches the tuple defined earlier. If multiple tuples match a template, the one returned by in is selected non- deterministically. Tuples can also be read from the tuple space using the non-destructive rd(p) operation. Both in and rd are blocking, i.e., if no matching tuple is available in
THE DESIGN OF LIGHTS
public interface ITupleSpace { String getName ();
void out(ITuple tuple);
void outg(ITuple[] tuples); ITuple in(ITuple template); ITuple inp(ITuple template); ITuple[] ing(ITuple template); ITuple rd(ITuple template); ITuple rdp(ITuple template); ITuple[] rdg(ITuple template); int count(ITuple template);
public interface ITuple {
ITuple add(IField field);
ITuple set(IField field, int index); IField get(int index);
ITuple insertAt(IField field, int index); ITuple removeAt(int index);
IField[] getFields();
int length ();
boolean matches(ITuple tuple);
public interface IField {
Class getType ();
IField setType(Class classObj); boolean matches(IField field);
public interface IValuedField extends IField {
boolean isFormal ();
java.io.Serializable getValue();
IValuedField setValue(java.io.Serializable obj);
Figure 1: The core interfaces of LighTS.
through the constructor, which also enables setting the name of the tuple space.
Tuples. Figure 1 shows the interface ITuple, which pro- vides methods for manipulating tuples. A field at a given position in the tuple (from 0 to length()-1) can be read (get), changed (set), or removed (removeAt). A new field can be appended at the end of the tuple (add), as well as at any other position (insertAt). The fields compos- ing the tuple can also be read collectively into an array (getFields). No syntactic distinction is made between tu- ples and templates—they are both ITuple objects.
The key functionality, however, is provided by the matches method, which is expected to embody the rules governing tuple matching and therefore is the one whose redefinition enables alternative semantics. This method is assumed to be automatically invoked by the run-time whenever a match must be resolved, and to proceed by comparing the tuple ob- ject on which matches is invoked—behaving as a template— against the tuple passed as a parameter. By virtue of en- capsulation, the matching rule implemented in matches is entirely dependent on the template’s class, implementing ITuple. Nevertheless, by virtue of polymorphism and dy- namic typing, the behavior of the run-time is the same re- gardless of the details of the matching rule, since the only assumption it makes is to operate on a template implement- ing ITuple.
The default semantics of matches as implemented in the built-in Tuple is the traditional one. When matches is in- voked on a template against a parameter tuple it returns true if:
1. the template and the tuple have the same arity, and
2. the ith template field matches the ith tuple field. Field matching is described next.
Fields. Figure 1 shows the interfaces representing tuple fields. IField provides the minimal abstraction of a typed tuple field. Methods are provided for accessing the field’s type (getType, setType). As with ITuple, IField contains a method matches, where the implementing classes specify the matching semantics, as exemplified later on.
The features of IField are enough to represent a for- mal but not an actual field, in that there is no notion of a field’s value. This abstraction is provided by the interface IValuedField which extends IField with the accessors nec- essary to deal with the value (getValue, setValue), as well as with a way to test whether the current field is a formal (isFormal). Note that setValue accepts any Object as a parameter. Moreover, the field’s type is automatically set to the parameter’s class.
The need for two separate interfaces is not immediately evident if one considers only the pragmatic need of sup- porting the basic Linda operations. As a matter of fact, the built-in Field implements both interfaces. However, this separation provides a cleaner decoupling when match- ing semantics that do not rely on exact value match are considered, as in the examples we provide later in this and the next section. The built-in Field is defined so that this.matches(f) returns true if:
1. this and f have the same type;
2. if this and f are both actuals (i.e., isFormal() returns
false for both of them) they also have the same value.
Equality of types and values is resolved by relying on the equals method—as done usually in Java. Also, a field that does not implement IValuedField is automatically consid- ered a formal.
Programming example. Let us walk through the simple task of inserting two tuples in a tuple space and retrieving one of them. We assume a statement import lights.* has been specified. First, we need to create a tuple space: ITupleSpace ts = new TupleSpace(“SAC05″);
Then, we need to create the two tuples. Fields can be cre-
IField f1 = new Field (). setValue (” Paolo “);
IField f2 = new Field().setValue(new Integer(10));
and then assembled in a tuple:
ITuple t1 = new Tuple().add(f1); t1.add(f2);
In alternative, we can leverage of the fact that ITuple meth- ods always return an ITuple object (although not strictly necessary from a purely semantic standpoint) and combine multiple statements in a single one:
new Tuple ()
.add(new Field().setValue(“Davide”)) .add(new Field().setValue(new Integer(20));
The tuples can be inserted one at a time, or together in a single atomic step, as in:
ts.outg(new ITuple[] = {t1, t2});
Templates are created just like tuples:
ITuple p = new Tuple ()
.add(new Field().setType(String.class)
.add(new Field().setValue(new Integer(10));
Finally, the probe operation
ITuple result = ts.rdp(p);
will return a copy of the first tuple in result. More exam- ples are available at [4] and [5].
3.2 Customizing LighTS
The LighTS framework is designed to provide the min- imal set of features implementing a Linda-like tuple space and, at the same time, to offer the necessary building blocks for customizing and extending it. We now discuss the most relevant customization opportunities, some of which are ac- tually exploited in the additional packages included in the LighTS distribution.
Changing the tuple space engine. The tuple space im- plementation in the lights core package is very simple3. Notably, the data structure holding tuples is simply an in- memory java.util.Vector object, which is scanned lin- early upon a query operation. This design is motivated by the need to support deployment on resource-constrained devices—a requirement of the Lime project—and admit- tedly may not perform reasonably in other scenarios.
Nevertheless, the information hiding provided by the core interfaces greatly simplifies the task of realizing more sophis- ticated implementations (e.g., providing persistence, check- pointing, or more scalable matching algorithms), with little or no impact on the application code. At one extreme, one could even sneak a commercial system (e.g., TSpaces or Gi- gaSpaces) behind the LighTS interfaces, e.g., to enable the development of applications that can be deployed on top of different tuple spaces engines. In a research context, this is particularly useful to evaluate different alternatives without the need to fully rewrite the application.
To make this development strategy easier, the lights.adap- ters package provides the building blocks necessary to sub- stitute the built-in implementation in lights with a dif- ferent one. The classes TupleSpace, Tuple, and Field in such package provide wrappers that on one hand implement the required lights interfaces, and on the other contain an adapter object implementing the required functionality, and to which interface operations are delegated4. The abstract class TupleSpaceFactory, to be derived by the actual adap- tation package, enables selection of the appropriate set of adapter
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com