Lime in a Nutshell
The Lime distribution is composed of four core packages:
limecontains the core functions of Lime, providing the transiently shared tuple space coordination abstraction.
Launcherclass, used for starting the runtime.
lime.util.consolecontains a graphical console for interacting with a
LimeTupleSpace, useful for understanding how the system works, and for debugging.
lime.mobileagent.mucodeprovides Lime-enabled mobile agents, through an adapter towards the µCode system. It also contains a
Launcherfor loading mobile agents.
- Although technically not Lime packages,
devutil.awtprovide utilities required by Lime.
Connectivity among hosts determines the sharing among interface tuple spaces to form the federated tuple space. The packages that help manage the connectivity are:
groupmgmtprovides an interface that triggers the Lime engagement/disengagement protocols when the group members have changed. A group is a set of mobile hosts that should be sharing their tuple spaces.
groupmgmt.implspecifies and implements the definition of a group. This includes prediction of disconnections based on safe-distance calculations.
locationdefines what location means in terms of information available from a GPS unit, including latitude, longitude, altitude, speed, etc.
Lime relies on three supplemental packages:
lightsprovides the underlying tuple space implementation necessary to run Lime in a package called LighTS.
mucodeprovides mobile agent capabilities for Lime agents with the µCode system. If mobile agents are not used, this package need not be included.
commprovides serial port access from Java. It is used specifically when Lime is connected with real GPS units.
Lime provides coordination among processes (Lime agents) via a shared memory mechanism. When processes use Lime to coordinate, no messages are explicitly sent to other processes. All communication occurs through access to a shared medium, namely the tuple space.
To understand Lime, one must
understand the notion of Lime agent (any thread implementing
lime.LimeAgent), transiently shared tuple space
LimeTupleSpace), tuple locations, engagement/disengagement of
hosts and agents, and reacting to changes in context.
Lime agents are the only active entities in Lime. They are programmatically
represented by Java threads implementing the lime.ILimeAgent interface.
Applications will typically subclass from the classes
lime.mobileagent.mucode.MobileAgent, which are provided by Lime and
implement the ILimeAgent interface.
Transiently Shared Tuple Spaces
The transiently shared tuple space concept is an extension of the standard Linda tuple space. Therefore, it is important to first understand the Linda tuple space model.
Linda. In Linda, a tuple space is a global and persistent
repository of tuples, essential data structures constituted by an
ordered sequence of typed fields. Every concurrent process in the system is
supposed to have access to the tuple space (hence the globality property),
which exists independently from the existence of the processes (hence the
persistency property). Linda provides a minimal interface to the tuple space,
with only three operations: one to write a tuple to the tuple space
out), one to get a copy of a tuple in the tuple space that
matches a given template (
rd), and a third that in addition to
getting a copy of a matching tuple withdraws it from the tuple space
in). In case of multiple matching tuples, one is returned
non-deterministically. The last two operations are blocking, i.e., if a
matching tuple is not found the caller process is suspended until a matching
tuple appears in the tuple space. In case of multiple processes blocked to
withdraw a tuple, when the tuple appears only one process, selected
non-deterministically, will receive the tuple. Instead, if the processes are
waiting to read a tuple, every process will get a copy of the tuple.
The figure above shows three Linda processes interacting with a single tuple space with the standard Linda operations.
Lime. Lime adapts this fundamental model of coordination and communication to encompass both physical and logical mobility. In Lime, agents (the active components in the system) can roam across mobile hosts (which act as mere containers for the agents), which can roam across the physical space. The presence of mobility prevents the existence of a global and persistent tuple space. Therefore, in Lime each mobile agent owns at least one Lime tuple space (LTS) that follows the agent during migration. The notion of a global and persistent tuple space is dynamically recreated on a host by merging the LTSs of all the mobile agents there co-located, thus creating a host-level transiently shared tuple space. Similarly, it is recreated across hosts by merging the host-level tuple spaces into a federated transiently shared tuple space. The contents of these tuple spaces are dynamically reconfigured by the system when an agent arrives or connection is established (tuple space engagement) and when an agent leaves or some host gets disconnected (tuple space disengagement). This way, Lime provides the programmer with the illusion of a global and persistent tuple space, which can still be accessed using the conventional Linda operations. It is this tuple space we refer to as the federated tuple space.
The figure above shows two agents on one host and three on another. The small
spheres represent the tuples of the same-colored agent. Because there is
connectivity between the hosts, the federated tuple space has the illusion of
containing the tuples of all agents on the hosts. In other words, an
in operation issued by any one of the agents can return a
matching tuple from the Lime tuple space of any agent.
Despite the illusion that Lime creates of a single shared memory space (the federated tuple space), it is inherently a distributed system and the tuples in the tuple spaces are physically stored across the multiple hosts in the system. In fact, each tuple is associated with a single agent (indicated in the figure by the color), and each tuple associated with an agent is stored on the same host where the agent is resident.
The standard tuple space operations
rd(p) intentionally ignore the distribution
of tuples across hosts by allowing location transparent access to the
tuple space. By default, the
out(t) operation associates the
tuple being written with the agent writing it. Both
rd(p) look for a matching tuple in the entire federated tuple
space, no matter which agent it is associated with. This view is very
powerful for simplifying applications.
Nevertheless, this view may hide too much information in cases where the
designer needs more fine-grained control over where tuples are placed and
where query operations are performed. The
out(t) with a location parameter
representing the identifier of the agent to be responsible for holding the
tuple (effectively allowing an agent to co-locate a tuple with another
agent). The semantics of
out(l,t) involve two steps. The first
step is equivalent to a conventional
out(t), the tuple
t is inserted in the local tuple space of the agent calling the
w. At this point the tuple
t has a
w, and a destination location
l. If the agent
l is currently connected, i.e.,
either co-located or located on a connected mobile host, the tuple
t is moved to the destination location. The combination of the
two actions are performed as a single atomic operation. On the other hand, if
l is not currently connected, the tuple remains with
w. This misplaced tuple, if not withdrawn, will remain
l becomes connected. In this case, the tuple will
migrate to the tuple space associated with
l as part of the
engagement transaction. Hence, using
out(l,t), the caller can
specify that the tuple, albeit shared, is supposed to be placed within the
tuple space of agent
l. This way, the default policy of keeping
the tuple in the caller's context until withdrawn can be overridden, and more
elaborate schemes for transient communication can be developed.
Location parameters also provide variants of the
rd(p) operations that allow access to a slice of the current
global context. In Lime, these operations are annotated as
rd(w,l,p), where the current
w) and destination (
l) locations described earlier
In a mobile environment, changes in connectivity among hosts are a normal occurrence as components move in and out of range of one another. The sets of connected hosts form dynamic communities which in Lime share their tuple spaces. The process of a host coming into range is referred to as engagement while the departure of a host is referred to as disengagement. Both engagement and disengagement are atomic. In other words, all hosts see the change of system configuration in the same order. During engagement, all misplaced tuples whose destination agent is now present are migrated to that destination. On disengagement, no tuples need to be migrated because they are already co-located with the agent responsible for them.
In Lime, we refer to a set of connected components as a group, and allow group-to-group engagement (i.e., the merging of two groups) as well as group-from-group disengagement (i.e., the partitioning of a single group into two). This is a slight departure from version 1.0 of Lime, which only allowed a single host to join or leave an existing group.
Lime 1.1 supports two forms of group management: beacon and safe distance.
- The first is based on the notion of detecting a periodic beacon from a host that is not already part of the group. This detection triggers the group-to-group engagement process. It is assumed that if a host wishes to disconnect from the group that it will stop beaconing before going out of range. This allows the disconnection process to terminate before the host is unreachable. This mechanism is useful for ad hoc settings such as small group meetings where hosts come into the room, start beaconing in order to join the group, and just before leaving stop beaconing in order to disconnect.
- The second attempts to remove the requirement that a host announce its departure by exploiting location, speed, and direction information (available from a GPS unit) to anticipate when a host is "about to" go out of range. Put another way, from the GPS information, the GroupManagement layer of Lime decides when a host is no longer within the safe distance for remaining in a group, and disengagement is triggered before the disconnection is lost. This mechanism is useful in the open environment such as a rescue operation where hosts carry GPS units and groups are formed dynamically based on location.
Reacting to Changes in Context
Mobility enables a highly dynamic environment, where reaction to change
constitutes a major fraction of the application design. In principle, Linda's
in(p) provides some degree of reactivity by allowing an
application to wait for a tuple, and then perform an action. Nevertheless, in
practice this solution has a number of well-known drawbacks that are a
consequence of the Linda perspective that expects agents to poll proactively
and synchronously the context for new events, rather than to specify the
actions to be executed reactively and asynchronously upon occurrence of an
Lime extends tuple spaces with a notion of reaction. A reaction is defined by a method to be executed when a tuple matching a specific pattern is found in the tuple space. The semantics of reactions are based on Mobile UNITY reactive statements, which all reactive statements are grouped to form a single reactive program. After each tuple space operation, the reactive program is run to fixed point. When no more matching tuples are found for any registered reaction, normal processing of tuple space operations resumes. Thus, reactions are executed atomically after each non-reactive statement. These semantics offer an adequate level of reactivity because all registered reactions are executed before the next regular tuple space operation executes.
Reactions are annotated with location parameters with the same meaning as
previously defined for
However, these so-called strong reactions are not allowed over
federated tuple spaces; in other words, the current location field must always
be specified and must be local to the subscriber. The reason for this lies in
the constraints introduced by physical mobility. If multiple hosts are
present, the content of the federated tuple space is physically distributed
among them. Maintaining the atomicity and serialization requirements of
reactive statements would require a distributed transaction encompassing
several hosts for every tuple space operation at any host---an
For these reasons, Lime provides also a notion of weak reaction.
Weak reactions are used primarily to detect changes to portions of the global
context that involve remote tuple spaces, such as those over the federated
tuple space. In this case, the host where the pattern is successfully matched
against a tuple, and the host where the corresponding action is executed are
different. Processing of a weak reaction proceeds as in the case of strong
reactions, except that the execution of the
reactsTo method does
not happen synchronously with the detection of a tuple matching. Instead, it
is guaranteed to take place eventually, if connectivity is preserved. The
ability to specify a weak reaction on the whole federated tuple space is an
extremely powerful programming tool, as it allows the programmer to describe
once and for all the actions to be performed in response to a given event,
independent of any changes in the system configuration.