Software composition with Linda

Nowadays, tuple spaces have turned out to be one of the most fundamental abstractions for coordinating communicating agents. Some models, as Linda, were presented as a set of inter-agent communication primitives which can virtually be added to any programming language. These models have the advantage of capturing both communication and synchronization in a natural and simple way. In this paper, we analyze the use of Linda to specify the interactive behavior of software components. We first introduce a process algebra for Linda and we define a notion of process compatibility that ensures the safe composition of components. This definition of compatibility takes into account the state of a global store (tuple space), which gives relevant information about the current execution of the system. Indeed, a Linda-based computation is characterized by the store's evolution, so that the set of tuples included into the store governs each computation step. In particular, we prove that compatibility implies successful computation (i.e. without deadlock). We also argue that Linda features some advantages with respect to similar proposals in the context of dynamic compatibility checking. In this context, the success of the composition of a pair of agents in presence of a suitable store can be useful to condition the acceptance of a given component into an open running system. In order to extend our approach to complex systems, where constructing a system involves more than two components, we propose the use of distributed tuple spaces as the glue to join components.     

Distributed programming with Logic Tuple Spaces

From the point of view of distributed programming one of the most interesting communication mechanisms is associative tuple matching in a shared dataspace, as exemplified in the Linda coordination language. Linda has been used as a coordination layer to parallelize several sequential programming languages, such as C and Scheme. In this paper we study the combination of Linda with a logic language, whose result is the language Extended Shared Prolog (ESP). We show that ESP is based on a new programming model called PoliS, that extends Linda with Multiple Tuple Spaces. A class of applications for ESP is discussed, introducing the concept of “open multiple tuple spaces”. Finally, we show how the distributed implementation of ESP uses the network version of Linda’s tuple space.     

Data Privacy in Tuple Space Based Mobile Agent Systems

More recently, distributed variants of tuple spaces have been proposed to exploit the Linda model for programming distributed applications over wide area networks, possibly exploiting code mobility. However, the flexibility of the shared tuple space model opens possible security holes; it basically provides no access protection to the shared data. In this paper we investigate some possible scenarios where mobile agents can benefit from our cryptographic tuple space based framework, CryptoKlava, and sketch how to possibly implement such agents in order to keep the privacy of items collected by the mobile agent during its itinerary. The functionalities of the framework are general enough to be applied to other Java frameworks using multiple distributed tuples spaces possibly dealing with code mobility.     

Supporting fault-tolerant parallel programming in Linda

Linda is a language for programming parallel applications whose most notable feature is a distributed shared memory called tuple space. While suitable for a wide variety of programs, one shortcoming of the language as commonly defined and implemented is a lack of support for writing programs that can tolerate failures in the underlying computing platform. This paper describes FT-Linda, a version of Linda that addresses this problem by providing two major enhancements that facilitate the writing of fault-tolerant applications: stable tuple spaces and atomic execution of tuple space operations. The former is a type of stable storage in which tuple values are guaranteed to persist across failures, while the latter allows collections of tuple operations to be executed in an all-or-nothing fashion despite failures and concurrency. The design of these enhancements is presented in detail and illustrated by examples drawn from both the Linda and fault-tolerance domains. An implementation of FT-Linda for a network of workstations is also described. The design is based on replicating the contents of stable tuple spaces to provide failure resilience and then updating the copies using atomic multicast. This strategy allows an efficient implementation in which only a single multicast message is needed for each atomic collection of tuple space operations     

Extension of scala language by distributed and parallel computing tools with Linda coordination system

The paper describes a new library developed for Linda language implementation for Scala programming language (language support of the component programming software). The library uses client-server architecture and a database for the tuple space representation. It implements the search for similarities and “primitive” and additional operations. The library can be used for distributed and parallel application development.     

Coordinating Mobile Agents by the XML-Based Tuple Space

This paper presents Xspace,a programmable coordination paradigm for Internet applications based on mobile agents.The Xspace system fully exploits the advantages of the XML language and Linda-like coordination.It supports XML documents as tuple fields and multiple matching routines implementing different relations among XML documents,including those given by XML query languages,The Xspace uses Java as the implementation language;it is based on object-oriented XMLized tuple spaces to implement a portable and programmable coordination paradigm for mobile agents.The dsign and implementation procedures of Xspace are described in this paper,Experiment and performance evaluation are also made.Finally,some conclusinos and remarks are given.     

Safe Composition of Linda-based Components

Component-Based Software Development is an emerging discipline in the field of Software Engineering. When constructing component-based systems, we must be sure that the cooperative behaviour of the components and their interaction will be successful. In this paper, we use Linda to specify the interactive behaviour of software components. To do this, we first introduce a process algebra for Linda, and then we define a compatibility relation providing conditions that ensure safe composition. This relation takes into account the state of a shared tuple space which represents the current execution. Indeed, a Linda-based computation is characterized by the store's evolution, so that the set of tuples included into the store governs each computation step. In this context, the success of the composition of a pair of agents in presence of a suitable store can be useful to condition the acceptance of a given component into an open running system. In order to extend our approach to complex systems, where constructing a system involves more than two components, we propose the use of distributed tuple spaces as the glue to join components.     

Instructional footprinting and semantic preservation in Linda

Linda is a co-ordination language designed to support process creation and interprocess communication within conventional computational languages. Although the Linda paradigm touts architectural and language independence, it often suffers performance penalties, particularly on local area network platforms. Instructional footprinting is an optimization technique with the primary goal of enhancing the execution speed of Linda programs. The two main aspects of instructional footprinting are instructional decomposition and code motion. The paper addresses the semantic issues encountered when the Linda primitives, IN and RD, are decomposed and moved past other Linda operations. Formal semantics are given as well as results showing significant speed-up (as high as 100%) when instructional footprinting is used.     

Coordinating Java agents over the WWW

We introduce Jada, a programming toolkit for coordinating agents written in Java. Coordination among either concurrent threads or distributed Java objects is achieved via shared object spaces. By exchanging objects through object spaces, Java agents or applets can exchange data or synchronize their actions over the Internet, a LAN, a single host, or even inside a Javaenabled browser. The access to an object space is performed using a set of methods of an ObjectSpace object. Such operations inspired by the Linda language are powerful enough to solve several coordination problems. Moreover, we show how Jada can be used as a coordination kernel for more complex coordination architectures.     

Distributed process creation within a shared data space framework

This paper describes the design and implementation of a remote process instantiation mechanism which is consistent with the Linda paradigm and semantics of the EVAL operation, and which uses shared data space as the medium for passing process and environment parameters. The motivation for such an implementation stems from our effort to rehost a uniprocessor version of the Linda computational system to a network of workstations. The baseline version of the Linda system relies on the semantics of the UNIX fork() system call to create processes and to pass the proper execution parameters to them. In creating a distributed version of the Linda environment, two major issues are addressed: (1) how to instantiate a remote process that knows where, among several possibilities, to begin its execution, and (2) how to communicate the proper run-time values of relevant variables to each new remote Linda process. Guiding our implementation was a desire to employ existing interprocess communication facilities, i.e. shared data space, to pass process creation and execution parameters.     

On the collective sort problem for distributed tuple spaces

In systems coordinated with a distributed set of tuple spaces, it is crucial to assist agents in retrieving the tuples they are interested in. This can be achieved by sorting techniques that group similar tuples together in the same tuple space, so that the position of a tuple can be inferred by similarity. Accordingly, we formulate the collective sort problem for distributed tuple spaces, where a set of agents is in charge of moving tuples up to a complete sort has been reached, namely, each of the N tuple spaces aggregate tuples belonging to one of the N kinds available. After pointing out the requirements for effectively tackling this problem, we propose a self-organizing solution resembling brood sorting performed by ants. This is based on simple agents that perform partial observations and accordingly take decisions on tuple movement. Convergence is addressed by a fully adaptive method for simulated annealing, based on noise tuples inserted and removed by agents on a need basis so as to avoid sub-optimal sorting. Emergence of sorting properties and scalability are evaluated through stochastic simulations.     

KLAIM: a kernel language for agents interaction and mobility

We investigate the issue of designing a kernel programming language for mobile computing and describe KLAIM, a language that supports a programming paradigm where processes, like data, can be moved from one computing environment to another. The language consists of a core Linda with multiple tuple spaces and of a set of operators for building processes. KLAIM naturally supports programming with explicit localities. Localities are first-class data (they can be manipulated like any other data), but the language provides coordination mechanisms to control the interaction protocols among located processes. The formal operational semantics is useful for discussing the design of the language and provides guidelines for implementations. KLAIM is equipped with a type system that statically checks access right violations of mobile agents. Types are used to describe the intentions (read, write, execute, etc.) of processes in relation to the various localities. The type system is used to determine the operations that processes want to perform at each locality, and to check whether they comply with the declared intentions and whether they have the necessary rights to perform the intended operations at the specific localities. Via a series of examples, we show that many mobile code programming paradigms can be naturally implemented in our kernel language. We also present a prototype implementation of KLAIM in Java     

Resource management in open Linda systems

Coordination systems, in particular Linda, have established themselves as important tools for the development of applications to open systems such as the Internet. This paper shows how to tackle a forgotten, but crucial problem in open coordination systems: memory management. As with any system which intends to be of wide use and because memory is a finite resource, coordination systems must address the problems of memory exhaustion. This paper first explores the orthogonality between coordination and computation in order to make it clear that the problem of memory exhaustion in coordination systems cannot be solved using garbage collection schemes implemented at the computation language—a garbage collection scheme must exist in the coordination environment as well. Following the explanation on orthogonality, the paper will focus on describing a garbage collection scheme for the Linda family of coordination systems. It is expected that the solution in Linda can be adapted to other coordination systems as long as they are based on tuple space communication. Copyright © 2003 John Wiley & Sons, Ltd.     

BaLinda Lisp: Design and implementation

BaLinda Lisp is a parallel Lisp dialect employing a shared memory model of parallel processing together with a subset of the Linda tuple space operators. Also included in the design is speculative processing. The aim is to have shared memory multiprocessing with the tuple space acting as the main data structure through which synchronization is done. The result is a flexible programming language. In this paper, we shall describe the design philosophy of BaLinda Lisp, discuss its implementation on three multiprocessing platforms, give examples of programs written in BaLinda Lisp and discuss future work on the language.     

Strategies and protocols for highly parallel Linda servers

The tuple space abstraction is a powerful and general coordination model for parallel and distributed programming. However, this model is based on the abstraction of a global space, difficult to implement in distributed memory parallel systems with high-performance and scalability. The paper discusses the possible distribution strategies to implement a tuple space server and proposes a new replication policy suitable for massively parallel systems. The proposed strategy achieves scalability by organising the system in a hierarchical way and by integrating coherence protocols of limited overhead. Moreover, the chosen organisation encourages the presence of multiple tuple spaces each with a constrained scope. The paper describes and analyses a transputer-based implementation: the hierarchical organisation of the tuple space makes the access time proportional to the locality of the references and bounded by the logarithm of the system size. © 1998 John Wiley & Sons, Ltd.     

A Fault-tolerant model for tuple space coordination in distributed environments

In distributed systems, tuple space is one of the coordination models that significantly maximizes system performance against failure due to its space and time decoupling features. With the growing popularity of distributed computing and increasing complexity in the network, host and link failure occurs frequently, resulting in poor system performance. This article proposes a fault-tolerant model named Tuple Space Replication (TSR) for tuple space coordination in distributed environments. The model introduces a multi-agent system that consists of multiple hosts. Each host in a multi-agent system comprises an agent space with a tuple space for coordination. In this model, we introduce three novel fault-tolerant algorithms for tuple space primitives to provide coordination among hosts with tolerance to multiple links and hosts failure. The first algorithm is given for out() operation to insert tuples in the tuple space. The second algorithm is presented for rdp() operation to read any tuple from the tuple space. The third algorithm is given for inp() operation to delete or withdraw tuples from the tuple space. These algorithms use less number of messages to ensure consistency in the system. The message complexity of the proposed algorithms is analyzed and found O(n) for out(), O(1) for rdp(), and O(n) for inp() operations which is comparable and better than existing works, where n is the number of hosts. The testbed experiment reveals that the proposed TSR model gives performance improvement up to 88%, 70.94%, and 63.80% for out(), rdp(), and inp() operations compared to existing models such as FT-SHE, LBTS, DEPSPACE, and E-DEPSPACE.     

Mobile Agent Coordination for Distributed Network Management

Mobile agents are a promising technology to face the problems raised by the increasing complexity and size of today's networks. In particular, in the area of network management, mobile agents can lead to a fully distributed paradigm to overcome the limits of traditional centralized approaches. A basic requirement for the management of a complex network is the definition of high-level and flexible models to coordinate the accesses to the resources—data and services—provided by the network nodes. On this basis, this paper describes the MARS coordination architecture for mobile agents. MARS is based on the definition of programmable tuple spaces associated with the network nodes: mobile agents can access the local resources and services via the tuple space, thus adopting a standard and high-level interface. The network administrator—via mobile agents—can dynamically program the behavior of the tuple space in reaction to the agents' access to the tuple space, thus leading to a flexible network model. Several examples show the effectiveness of the MARS approach in supporting network management activities.     

Linda meets Unix

The limitations of the shared-memory and distributed-memory models for explicit parallel programming are discussed and a new model, the Linda parallel communication paradigm which was designed specifically for parallel programming, is examined. Processes communicate in Linda by way of a shared data space called tuple space which acts something like an associative memory, since tuples are identified by matching on a key rather than using a specific address. This model is adapted for use as the basis of a new class of operating systems and a specific instance, QIX, is presented. Like Linda, this operating system model can support both the shared-memory and the distributed-memory styles of programming. Thus, it provides the benefits of both, while avoiding hardware dependencies. QIX also incorporates a novel scheme for name resolution that is easier to use than other methods and provides significant benefits in the operating system and it directly supports communication between programs written in different languages     

An architecture for tuple‐based coordination of multi‐agent systems

Multi‐agent system development calls for powerful and expressive coordination models and languages, as well as for an effective coordination technology. A good deal of the current research effort focuses on tuple‐based coordination, exploiting its well‐known advantages, such as agent uncoupling and associative access to information, and addressing its limitations in terms of flexibility and control capabilities. In particular, the behaviour of a Linda‐like tuple space is fixed once and for all by the coordination model, and cannot be tailored to the specific application needs. Tuple centres are tuple spaces whose behaviour can be programmed by defining transactional reactions to the basic communication events, allowing coordination laws to be explicitly defined and embedded into the coordination medium. This paper presents the architecture of a run‐time system for tuple‐based coordination, where tuple centres work as an extensible kernel, around which multi‐agent systems can be designed and deployed. After sketching the implementation, the paper shows the advantages that can be achieved from both the design and the performance viewpoints. Copyright © 1999 John Wiley & Sons, Ltd.     

Dispel: A run-time debugging language

Dispel is a language designed to aid communication between an interactive user and a run-time, symbolic debugging system. Important attributes of Dispel are that it provides a small set of primitive debugging actions, most traditional debugging aids (such as variable traces and postmortem dumps) are written in terms of these primitives as debugging routines, and Dispel serves both as an interactive debugging command language and as a special-purpose programming language. The syntax and semantics of Dispel are explained and examples of Dispel commands and routines are presented.