Search

Packet classification is a critical component in network appliances. Software Defined Networking and cloud computing update the rulesets frequently for flexible policy configuration. Tuple Space Search (TSS), implemented in Open vSwitch (OVS), achieves fast rule updating at the sacrifice of the classification rate. In TSS, each tuple is managed by a hash table and classifying a packet needs to go through all hash tables. Merging tuples can reduce the number of hash tables, but inevitably increases the hash conflicts that may even worsen the classification performance in some cases. No existing algorithm meets the need of both fast packet classification and online rule updating. In this paper, we propose Convolutional Neural Network (CNN)-based Range Partition (CRP) to achieve fast packet classification and online update simultaneously. CRP exploits CNN-based image recognition to quickly partition tuples into range spaces upon the change of ruleset distribution, which reduces hash operations while avoiding rule overlapping caused by hashing many rules to the same location of the hash table. Experimental results demonstrate that CRP achieves 3.2x classification speed and 4.2x update speed on average compared with state-of-the-art algorithms. We also implement CRP in OVS. The throughput of CRP-OVS is 10x that of native OVS.

Actors collaborate via message exchanges to reach a common goal. Experience has shown, however, that pure message-based communication is limiting and forces developers to use design patterns. The recently introduced dataspace actor model borrows ideas from the tuple space realm. It offers a tightly controlled, shared storage facility for groups of actors. In this model, actors assert facts that they wish to share and interests in such assertions. The dataspace notifies interested parties of changes to the set of assertions that they are interested in. Although it is straightforward to add the dataspace model to untyped languages, adding a typed interface is both necessary and challenging. Without restrictions on exchanged data, a faulty actor may propagate erroneous data through a malformed assertion, causing an otherwise well-behaved actor to crash—violating the key principle of failure isolation. A properly designed type system can prevent this scenario and rule out other kinds of uncooperative actors. This paper presents the first structural type system for the dataspace model of actors; it does not address the question of behavioral types for assertion-oriented protocols.

Rainfall is a smart contract programming model that allows mutually distrusting parties to manage assets on a distributed ledger. The model consists of a tuple space of authorized facts, and a set of production rules. Rules match on authorized facts, gaining their authority, and produce new facts with a subset of the gained authority. Rainfall allows assets such as crypto currencies to be defined in user code, rather than being baked directly into the ledger framework. Our authorization model also provides a natural privacy model, where not all rules or facts need to be revealed to all parties.

A challenging aspect of The Internet of Things (IoT) is to provide an architecture that can handle the range of IoT elements ranging from Cloud-based applications to constrained nodes in Wireless Sensor Networks (WSNs). Such an architecture must be scalable, allow seamless operation across networks and devices with little human intervention. This paper describes a set of abstractions and an architecture for the flow of data from sensors to applications supported by a Distributed Hash Table (DHT) and our novel Holistic Peer to Peer (HPP) Application Layer protocol to handle node ids, capabilities, services and sensor data. We show that this architecture can operate in a constrained node by presenting a `C' implementation running on the Contiki3.0 OS and consider the effectiveness of its use of a DHT and its abstractions.

Preprint de: A. Pérez-Vereda, C. Canal, E. Pimentel. Modelling Digital Avatars: a tuple space approach, Science of Computer Programming, vol. 203, Elsevier, 2020, DOI: https://doi.org/10.1016/j.scico.2020.102583. The development of the Internet of Things (IoT) came with the manufacturing of a huge amount of smart things equipped with sensors for making them aware of their environment, and with network connection for allowing remote interaction with them. However, most smart things still lack enough autonomy and context-awareness, hindering them from being people-friendly and actually useful for their users' everyday tasks. IoT devices should take advantage of their sensors and smartness to react automatically to the needs of their users and to provide seamless interactions with them. Within this field, the authors work on the design of Digital Avatars, a mobile computing framework for dynamically programming interactions among smart devices. The framework is based on the virtual profile of the user, which is inferred, stored, and shared by their smartphone. The profile provides a personalized context for running scripts which interact with IoT devices. This way, smartphones become a digital avatar of the user, capable of acting as a personal and seamless interface with their IoT environment. In this work, we present a formalization of Digital Avatars by means of a Linda-based approach with multiple shared tuple spaces. By means of a case study, we show how properties of the systems can be proved, and we briefly describe an implementation of both the Digital Avatars framework and the case study.

International audience; Major challenges in the software development of distributed systems are rooted in the complex nature of coordination. Assertions are a practical programming mechanism to improve the quality of software in general by monitoring it at runtime. Most approaches today limit assertions to statements about local states whereas coordination requires reasoning about distributed states. The Peer Model is an event-based coordination programming model that relies on known foundations like shared tuple spaces, Actor Model, and Petri Nets. We extend it with distributed runtime invariant assertions that are specified and implemented using its own coordination mechanisms. This lifts the concept of runtime assertions to the level of coordination modeling. The concept is demonstrated by means of an example from the railway domain.

Coordination languages have been proved very suitable for modeling and programming service-oriented applications. In particular, those based on tuple spaces offer an elegant way of making different components of such applications interact smoothly through the deposit and retrieval of tuples in a shared space. However, in their basic form, these languages only allow one tuple to be put at a time and, when more than one tuple matches a required one, the selection is made non-deterministically. This is obviously too weak to capture popularity or quality measures, which are nevertheless central in service-oriented applications. To that end, we propose an extension of a Linda-like language aiming at promoting the notion of density and, based on De Boer and Palamidessi's notion of modular embedding, study its expressiveness. We prove accordingly that it strictly increases the expressiveness of Linda while keeping the same implementation efficiency. We also compare it with languages based on multiset rewriting, such as Gamma, and establish that, although it is less expressive, it benefits from a much more efficient scheme. Finally we study the hierarchy of the sublanguages induced by considering subsets of tuple primitives and prove that it follows that of the Linda family of languages. We propose an extension of a Linda-like language promoting the notion of density.Based on De Boer and Palamidessi's notion of modular embedding, we study its expressiveness.We prove that it strictly increases the expressiveness of Linda.We prove that it is less expressive than languages based on multi-set rewriting.We study the hierarchy of the sublanguages induced by subsets of tuple primitives.

Security policies are important for protecting digitalized information, control resource access and maintain secure data storage. This work presents the development of a policy language to transparently incorporate aggregate programming and privacy models for distributed data. We use tuple spaces as a convenient abstraction for storage and coordination. The language has been designed to accommodate well-known models such as k-anonymity and \((\varepsilon ,\delta )\)-differential privacy, as well as to provide generic user-defined policies. The formal semantics of the policy language and its enforcement mechanism is presented in a manner that abstracts away from a specific tuple space coordination language. To showcase our approach, an open-source software library has been developed in the Go programming language and applied to a typical coordination pattern used in aggregate programming applications.

With the fast development of Software Defined Networking (SDN) and network virtualization, software-based network virtual switches have emerged as a critical component to provide network services to VMs. Among virtual switches, Open vSwitch (OvS) is an open source virtual switch implementation commonly used and well-studied. Using Data Plane Development Kit (DPDK) with OvS to bypass the OS kernel and process packets in userspace provides tremendous performance benefits on general purpose platforms. Integrated GPUs, residing on the same die with the CPU on general purpose platforms, offering many advanced features such as on-chip interconnect CPU-GPU communication, and sharing physical/virtual memory, become a promising additional compute resource to further accelerate the OvS process. In this paper, we design and implement an inline GPU assisted OvS architecture, via offloading the expensive tuple space search to GPU and balancing switching processing between CPU and GPU. We evaluated the performance on an Intel® Xeon® processor of the E3-1575M v5 product family (code-name Skylake) with an integrated GT4e GPU. The results show that our proposed architecture improved the OvS throughput by 3x, compared to the optimized CPU-only OvS-DPDK implementation.

Highly dynamic distributed applications often require flexible coordination among several autonomous components. Space-based middleware provides a suitable, data-driven coordination paradigm for such scenarios, where distributed peers exchange data and commands in a scalable and decoupled way using shared tuple spaces. In its basic form, such a middleware supports access to a data storage and (blocking) queries on the stored tuples. However, in many cases the injection of additional server-side logic would ease the development of complex applications, as the semantics of the tuple space can be adapted to domain-specific requirements.This paper introduces reactive programming features for XVSM, a space-based middleware that enhances the tuple space concept with powerful coordination mechanisms. We present a comprehensive extension mechanism that supports the execution of application logic in reaction to composite and time-based events. As an example for the feasibility of the approach, we provide a bootstrapped solution for a leasing mechanism that manages the lifetime of data in the space.

Packet classification is an important part of many networking devices, such as routers and firewalls. Software-defined networks require online packet classification where classifiers receive a mixed stream of packets to classify and rules to update and both operations must be completed as efficiently as possible without knowledge of future operations. This rules out many classifiers, such as HyperCuts, HyperSplit, and their derivatives, which do not support fast updates. We build upon Tuple Space Search, the packet classifier used by Open vSwitch, to create TupleMerge. TupleMerge improves upon Tuple Space Search by combining hash tables which contain rules with similar characteristics. This greatly reduces classification time by producing fewer tables. We compared TupleMerge to PartitionSort, the current state-of-the-art online packet classifier, on rulelists generated by ClassBench. TupleMerge outperforms PartitionSort at both classifying packets and rule update. Specifically, on average, it is 34.2% faster at classifying packets and 30% faster at updating rules than PS.

none 4 no Available online 20 September 2016 Rollback is a fundamental technique for ensuring reliability of systems, allowing one, in case of troubles, to recover a past system state. However, the definition of rollback in a concurrent/distributed scenario is quite tricky. We propose an approach based on the notion of causal-consistent reversibility: any given past action can be undone, provided that all the actions caused by it are undone as well. Given that, we define a rollback as the minimal causal-consistent sequence of backward steps able to undo a given action. We define the semantics of such a rollback operator, and show that it satisfies the above specification. The approach that we present is quite general, but we instantiate it in the case of μKlaim, a formal coordination language based on distributed tuple spaces. We remark that this is the first definition of causal-consistent rollback in a shared-memory setting. We illustrate the use of rollback in μKlaim on a simple, but realistic, application scenario. open Giachino, Elena; Lanese, Ivan; Mezzina, Claudio Antares; Tiezzi, Francesco Giachino, Elena; Lanese, Ivan; Mezzina, Claudio Antares; Tiezzi, Francesco

Extracting tuples from HTML pages has been an important issue in various web applications. Commercial tuple extraction systems have enjoyed some success to extract tuples by regarding HTML pages as tree structures and exploiting XPath queries to find attributes of tuples in the HTML pages. However, such systems would be vulnerable to small changes on the web pages. In this paper, we propose a robust tuple extraction system which utilizes spatial relationships among elements rather than the XPath queries. Spatial information (e.g., 2-D coordinates) of elements are maintained in the DOM tree when a web page is rendered in a browser. Our system regards elements in the rendered page as spatial objects in the 2-D space and executes spatial joins to extract target elements. Since humans also identify an element in a web page by its relative spatial location, our system extracting elements by their spatial relationships could possibly be as robust as manual extraction. To specify and execute spatial joins, we propose a new query language, RAQuery, based on topological relationships between any spatial objects in the 2-D space. We then propose spatial join algorithms that efficiently process the RAQuery using novel notions of group match and prunable relation group. We next propose a tuple construction algorithm to build tuples from the extracted elements obtained by the spatial joins, which can construct tuples even when there are no boundary HTML elements specified for the tuples in the web page. Extensive experimental results using real HTML pages confirm that our solutions are far more robust than existing tuple extraction systems without sacrificing performance.

In Ambient Intelligence environments machines proactively and transparently work on behalf of humans. The nature of these machines and the communication protocols they use is multifarious. Therefore, the applications running on top of them remarkably demand interoperability. The Triple Space Computing (TSC) paradigm addresses that problem by sharing information represented in a semantic format through a common virtual space. As long as application developers use standard ontologies, different applications using the same spaces will interact automatically. The focus of this paper is to present Otsopack, a fully distributed TSC middleware designed to meet the needs of mobile and resource constrained devices. Otsopack defines a simple HTTP interface for the TSC operations. This interface focuses on simplicity and modularity, so that two implementations that support different modules can still interact. To assess the middleware we provide time and load measurements, and we analyze two independent implementations.

In this paper we introduce a new Platform-as-a-Service cloud environment that combines the LINDA coordination language, an in-memory key-value store, with functional programming to facilitate efficient execution of tenant plugins and applications. In the implementation a tuple space plays a central role in introducing deterministic services for basic parallel programming, including message passing, persistent infinite message pools and transactions. Redis, a key-value store, serves as the in-memory tuple space that glues together parallel constructs (i.e. skeletons) of formerly monolithic business applications to form an elastic distributed application. Although functional programming languages have adopted new runtime technology to achieve parallel execu- tion, which is mostly focused on threads, it rarely offers an obvious way to match functions to threads. We find that the LINDA tuple space and its coordination model offers a general purpose paradigm to tackle synchronisation issues that ties into both domains of computing clouds: computation through supporting common skeletons and big data (analytics) through serving as an in-memory data grid.

Data analytics applications handle large data sets subject to multiple processing phases, some of which can execute in parallel on clusters, grids or clouds. Such applications can benefit from using MapReduce model, only requiring the end-user to define the application algorithms for input data processing and the map and reduce functions, but this poses a need to install/configure specific frameworks such as Apache Hadoop or Elastic MapReduce in Amazon Cloud. In order to provide more flexibility in defining and adjusting the application configurations, as well as in the specification of the composition of the application phases and their orchestration, the authors describe an approach for supporting MapReduce stages as sub-workflows in the AWARD framework (Autonomic Workflow Activities Reconfigurable and Dynamic). The authors discuss how a text mining application is represented as a complex workflow with multiple phases, where individual workflow nodes support MapReduce computations. Access to intermediate data produced during the MapReduce computations is supported by a data sharing abstraction. The authors describe two implementations of this abstraction, one based on a shared tuple space and another based on an in-memory distributed key/value store. The authors describe the implementation of the framework, a set of developed tools, and our experimentation with the execution of the text mining algorithm over multiple Amazon EC2 (Elastic Compute Cloud) instances, and report on the speed-up and size-up results obtained up to 20 EC2 instances and for different corpus sizes, up to 97 million words.

The paper presents MorphicLib, a new partial homomorphic cryptography library written in Java that can be used to implement a wide-range of applications. The paper shows the use of the library with the HomomorphicSpace coordination service. This service is a tuple space that stores encrypted tuples but still supports operations like returning tuples with values within a certain range.

In recent years, plenty of research has been done related to the methods of composition of web services. Notwithstanding much effort, it seems that this technology has a long way till it attains perfection. In this research, providing a suggestive model, we performed service orchestration semi-centrally. To do this, we need to group web services. We created groups or clusters of web services and put services in appropriate groups, by this way, the number of control flow and data flow notifications decreases considerably. For each group a controller and a Tuple space is considered and the controller is responsible for invoking services of that group Simulation results show that service orchestration can be influential in decreasing the amount of traffic, especially in composite services with a high level of communication in their component services. In addition, a decrease in the level of distribution in service orchestration can improve capability of execution monitoring and failure compensation.

The content aware (CA) packet classification and processing at network level is a new approach leading to significant increase of delivery quality of the multimedia traffic in Internet. This paper presents a solution for a new multi-dimensional packet classifier of an edge router, based on content - related new fields embedded in the data packets. The technique is applicable to content aware networks. The classification algorithm is using three new packet fields named Virtual Content Aware Network (VCAN), Service Type (STYPE), and U (unicast/multicast) which are part of the Content Awareness Transport Information (CATI) header. A CATI header is inserted into the transmitted data packets at the Service/Content Provider server side, in accordance with the media service definition, and enables the content awareness features at a new overlay Content Aware Network layer. The functionality of the CATI header within the classification process is then analyzed. Two possibilities are considered: the adaptation of the Lucent Bit vector algorithm and, respectively, of the tuple space search, in order to respond to the suggested multi-fields classifier. The results are very promising and they prove that theoretical model of inserting new packet fields for content aware classification can be implemented and can work in a real time classifier.

In differentiated services, packet classification is used to categorize incoming packets into multiple forwarding classes based on pre-defined filters and make information accessible for quality of service. Although numerous algorithms have presented novel data structures to improve the search performance of packet classification, the performance of these algorithms are usually limited by the characteristics of filter databases. In this paper, we use a different approach of filter preprocessing to enhance the search performance of packet classification. Before generating the searchable data structures, we cluster filters in a bottom-up manner. The procedure of the filter clustering merges filters with high degrees of similarity. The experimental results show that the technique of filter clustering could significantly improve the search performance of Pruned Tuple Space Search, a notable hash-based algorithm. As compared to the prominent existing algorithms, our enhanced Pruned Tuple Space Searchalso has superior performance in terms of speed and space.

The safety of dikes in The Netherlands, located in the delta of the rivers Rhine, Meuse and Scheldt, has been the subject of debate for more than ten years. The safety (or flood risk) of a particular area may depend on the safety of other areas. This is referred to as effects of river system behaviour on flood risk (quantified as the estimated number of casualties and economic damage). A computational framework was developed to assess these effects. It consists of several components that are loosely coupled via data files and Tcl scripts to manage the individual programs and keep track of the state of the computations. The computations involved are lengthy (days or even weeks on a Linux cluster), which makes the framework currently more suitable for planning and design than for real-time operation. While the framework was constructedad hoc, it can also be viewed more formally as atuplespaceRealising this makes it possible to adopt the philosophy for other similar frameworks.

The computational grid is rapidly evolving into a large-scale computing infrastructure that facilitates resource sharing and problem solving over the Internet. Information services play a crucial role in grid environments for discovery of resources. The dynamic nature and the large-scale of a grid pose many challenges to information services in terms of scalability and resilience. This paper presents RDSpace which can be used as a substrate for resource discovery in grid environments. RDSpace builds a shared tuple space on top of a structured peer-to-peer overlay to achieve high scalability in dealing with a large number of computing nodes and to support range queries in discovery of resources. Another novelty of RDSpace lies in its capability to handle churn situations where nodes may join or leave the space frequently. RDSpace is evaluated from the aspects of scalability and churn handling, and the evaluation results are also presented in this paper.

The Semantic Web is about a Web which contains data which is machine-processable rather than human-interpretable. This makes new demands upon the Web architecture such as a standardized interface for access to this knowledge (how to interact), model and vocabulary-based mediation (how to understand) and semantic-based distribution (how to find). We present a middleware based on the concepts of co-ordination and space-based computing as a proposed part of the necessary Semantic Web architecture and outline its usage in the Web-based utilization of distributed knowledge.

The Internet of Things (IoT) is here: smart objects are pervading our everyday life. Smart devices automatically collect and exchange data of various kinds, directly gathered from sensors or generated by aggregations. Suitable coordination primitives and analysis mechanisms are in order to design and reason about IoT systems, and to intercept the implied technology shifts. We address these issues by defining IoT-LySa, a process calculus endowed with a static analysis that tracks the provenance and the route of IoT data, and detects how they affect the behaviour of smart objects.

Among the paradigms for parallel and distributed computing, the one popularized with Linda and based on tuple spaces is the least used one, despite the fact of being intuitive, easy to understand and to use. A tuple space is a repository of tuples, where process can add, withdraw or read tuples by means of atomic operations. Tuples may contain different values, and processes can inspect the content of a tuple via pattern matching. The lack of a reference implementations for this paradigm has prevented its widespread. In this paper, first we do an extensive analysis on what are the state of the art implementations and summarise their characteristics. Then we select three implementations of the tuple space paradigm and compare their performances on three different case studies that aim at stressing different aspects of computing such as communication, data manipulation, and cpu usage. After reasoning on strengths and weaknesses of the three implementations, we conclude with some recommendations for future work towards building an effective implementation of the tuple space paradigm.

The implementation of a distributed self-aware computing system (SACS) typically requires a substantial software infrastructure. A middleware system with dedicated services for self-awareness and self-expression can therefore support the development of SACS applications. In this chapter we show the advantages of using a middleware system as the basis for a self-aware computing system. We identify requirements for middleware systems to support the development of self-aware applications. By providing facilities for communication, decoupling and transparency, middleware systems can provide essential features needed in SACS. We compare different middleware paradigms and their suitability to support self-awareness in distributed applications. We argue that the publish/subscribe paradigm is very well suited for this application area since it supports modularisation and decoupling. Units can be added to and removed from existing applications and may well be reused in new applications. Thus, SACS can be constructed by recombining existing publish/subscribe modules. In addition, we present details of publish/subscribe and introduce our middleware implementation called Ella. We describe how different aspects of a SACS and patterns for self-aware applications can be represented using Ella. We present different communication paradigms in Ella (broadcasting, peer2peer) as well as decoupling mechanisms provided by the middleware. We argue that SACS applications can be developed (i) faster, (ii) more efficiently and (iii) more reliable with Ella. Finally, Chapter 13 presents a self-aware and self-expressive multi-camera application which has been implemented with Ella.

In this chapter a novel approach to coordination in situated Multi-Agent Systems (MAS) is described, by presenting a meta-model for situated MAS engineering, an architecture for the design of tuplespace-based middleware for situated coordination, and a language dealing with situatedness-related issues. Accordingly, a review of meta-models and architectures from an historical perspective discusses their evolution, up to a reference meta-model and abstract architecture (Sect. 4.1); then, instantiation of the reference architecture on the TuCSoN middleware is described, focussing on the issue of environmental situatedness (Sect. 4.2); finally, spatial situatedness is analysed, by describing how the ReSpecT language deals with it (Sect. 4.3).

In this chapter, we present and explain the Blackboard architectural style and how to specify it in SysADL. We specify the style using the structural and behavioral views. Finally, we illustrate the Blackboard style and how to use it with our running example.

With the advancements in multi-core CPU architectures, it is now possible for a server operating system (OS) such as Linux to handle a large number of concurrent application services on a single server instance. Individual service components of such services may run in different isolated environments, such as chrooted jails or application containers, and may need controlled access to system resources and the ability to collaborate and coordinate with each other in a regulated and secure manner. In an earlier work, we motivated the need for an access control framework that is based on the principle of least privilege for formulation, management, and enforcement of policies that allows controlled access to system resources and also permits controlled collaboration and coordination for service components deployed in disjoint containerized environments under a single OS instance. The current work provides a more in-depth treatment of secure inter-component communication in such environments. We show the policies needed for such communication and demonstrate how they can be enforced through a Linux Policy Machine that acts as the centralized reference monitor. The inter-component interaction occurs through the persistent layer using a tuple space abstraction. We implemented a tuple space library that provides operations on the tuple space. We present preliminary experimental results of its implementation that discuss the resource usage and performance.

This chapter compares and contrasts different approaches to specifying control flow and different implementations of the approaches in programming languages. Thus far, mostly μC++ has been used to specify advanced control flow; it is important to look at other approaches to see if there are strong or weak equivalences among them.

Research on peer-to-peer (P2P) networks has attracted much attention recently. A key factor is their ability to handle dynamics in the system in a distributed fashion, including ad hoc and dynamic join and departure of the peers and dynamic changes in the underlying network environment. As more and more innovating P2P applications appear, the need to support intuitive communication and synchronization among the peers in the P2P system becomes imperative. In this paper, we discuss how to build a tuple space on top of P2P systems and use on-line games as a target application. A simple API is supported for accessing the data stored in the tuple space and communicating between the peers. Through experiments and a demonstration game, we show that our system can facilitate the development of network games in a fully distributed environment.

International audience; With the emergence of Future Internet applications that connect web services, sensor-actuator networks and service feeds, scalability and heterogeneity support of interaction paradigms are of critical importance. Heterogeneous interactions can be abstractly represented by client-service, publish-subscribe and tuple space middleware connectors that are interconnected via bridging mechanisms providing interoperability among the services. In this paper, we make use of the eXtensible Service Bus (XSB), proposed in the CHOReOS project as the connector enabling interoperability among heterogeneous choreography participants. XSB models transactions among peers through generic post and get operations that represent peer behavior with varying time/space coupling. Nevertheless, the heterogeneous lease and timeout constraints of these operations severely affect latency and success rates of transactions. By precisely studying the related timing thresholds using timed automata models, we verify conditions for successful transactions with XSB connectors. Furthermore, we statistically analyze through simulations, the effect of varying lease and timeout periods to ensure higher probabilities of successful transactions. Simulation experiments are compared with experiments run on the XSB implementation testbed to evaluate the accuracy of results. This work can provide application developers with precise design time information when setting these timing thresholds in order to ensure accurate runtime behavior.

In tuplespace applications where flows of data need to be kept separate for confidentiality reasons, there must be a rights management arrangement to control the access to tuples. Also, where the authorization of the tuple creator needs to be controlled for integrity reasons, the same requirement applies. This paper describes the SmallSpaces tuplespace implementation and how the implementation meets these requirements. Firthermore, the arrangement for the protection from covert channels during transaction processing is discussed.

This paper discusses the current resurgence of interest in the Linda coordination language for parallel and distributed programming. Particularly in the Java field, there have been a number of developments over the past few years. These developments are summarised together with the advantages of using Linda for programming concurrent systems. Some problems with the basic Linda approach are also discussed and a novel solution to these is presented. The power and flexibility of the proposed extensions to the Linda programming model are illustrated by considering a number of example applications, including a detailed case study of visual language parsing.

Leveraged by the success of applications aiming at the ‘free’ sharing of data in the Internet, the paradigm of peer-to-peer (P2P) computing has had substantial consideration devoted to it recently. This paper presents a high-level abstraction for remote object interaction in a P2P environment, called borrow/lend (BL). We present the principles underlying our BL abstraction, and illustrate how this abstraction can be used to program P2P applications in Java. We contrast our abstraction with established abstractions for distributed programming such as the remote method invocation or the tuple space, illustrating how the BL abstraction, obviously influenced by such previous abstractions, unifies flavors of these, but also how it captures the constraints specific to P2P environments. Copyright © 2005 John Wiley & Sons, Ltd.

In this paper, we apply market mechanism and agent to build grid resource management, where grid resource consumers and providers can buy and sell computing resource based on an underlying economic architecture. All market participants in the grid environment including computing resources and services can be represented as agents. Market participant is registered with a Grid Market Manager. A grid market participant can be a service agent that provides the actual grid service to the other market participants. Grid market participants communicate with each other by communication space that is an implementation of tuple space. In this paper, Grid agent model description is given. Then, the structure of Grid Market is described in detail. The design and implementation of agent oriented and market oriented grid resource management are presented in this paper.

We present the modelling language, Klaim-DB, for distributed database applications. Klaim-DB borrows the distributed nets of the coordination language Klaim but essentially re-incarnates the tuple spaces of Klaim as databases, and provides high-level language abstractions for the access and manipulation of structured data, with integrity and atomicity considerations. We present the formal semantics of Klaim-DB and illustrate the use of the language in a scenario where the sales from different branches of a chain of department stores are aggregated from their local databases. It can be seen that raising the abstraction level and encapsulating integrity checks (concerning the schema of tables, etc.) in the language primitives for database operations benefit the modelling task considerably.

International audience; Causal-consistent reversibility is a natural way of undoing concurrent computations. We study causal-consistent reversibility in the context of µKLAIM, a formal coordination language based on distributed tuple spaces. We consider both uncontrolled reversibility, suitable to study the basic properties of the reversibility mechanism, and controlled reversibility based on a rollback operator, more suitable for programming applications. The causality structure of the language, and thus the definition of its reversible semantics, differs from all the reversible languages in the literature because of its generative communication paradigm. In particular, the reversible behavior of µKLAIM read primitive, reading a tuple without consuming it, cannot be matched using channel-based communication. We illustrate the reversible extensions of µKLAIM on a simple, but realistic, application scenario.

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 design and implementation procedures of Xspace are described in this paper. Experiment and performance evaluation are also made. Finally, some conclusions and remarks are given.

Coordination languages are an established programming model for distributed computing, but have been largely eclipsed by message passing (MPI) in scientific computing. In contrast to MPI, parallel workers never directly communicate, instead "coordinating" indirectly via key-value store puts and gets. Coordination often focuses on program expressiveness, making parallel codes easier to implement. However, coordination also benefits resilience since the key-value store acts as a virtualization layer. Coordination languages (notably Linda) were therefore leading candidates for fault-tolerance in the early '90s. We present the FOX tuple space framework, an extension of Linda ideas focused primarily on transitioning MPI codes to coordination programming. We demonstrate the notion of "MPI Perturbation Theory," showing how MPI codes can be naturally generalized to the tuple-space framework. We also consider details of high-performance interconnects, showing how intelligent use of RDMA hardware allows virtualization with minimal added latency. The framework is shown to be resilient to degradation of individual nodes, automatically rebalancing for minimal performance loss. Future fault-tolerant extensions are discussed.

Linda is a high-level coordination model that allows agents to interact via shared tuplespaces without knowing each other's identities and without having to arrange for a definite rendezvous. This high level of abstraction would make Linda particularly suitable for use as a coordination model for heterogeneous distributed systems, if it were not for the fact that the Linda communication is unsafe. In order to enhance the safety of tuplespaces, this article introduces a mechanism for establishing security policies that regulate agent access to tuplespaces. This mechanism is based on a previously published concept of law-governed interaction. It makes a strict separation between the formal statement of a policy, which one calls a "law," and the enforcement of this law, which is carried out by a set of policy-independent trusted controllers. A new policy under this scheme is created basically by formulating its law, and can be easily deployed throughout a distributed system. Two example policies are discusse...

Coordination languages for parallel and distributed systems specify mechanisms for creating tasks and communicating data among them. These languages typically assume that (a) once a task begins execution on some processor, it will remain resident on that processor throughout its lifetime, and (b) communicating shared data among tasks is through some form of message-passing and data migration. In this paper, we investigate an alternative approach to understanding coordination. Communication-passing style (CmPS) refers to a coordination semantics in which data communication is always undertaken by migrating the continuation of the task requiring the data to the processor where the data resides. Communication-passing style is closely related to continuation-passing style (CPS), a useful transformation for compiling functional languages. Just as CPS eliminates implicit call-return sequences, CmPS eliminates implicit inter-processor data communication and synchronization requests. In a CmPS-transformed program, only continuations (i.e., control contexts) are transmitted across machines; all synchronization and data communication occurs locally. Besides providing significant optimization opportunities, CmPS is a natural representation for implementations on networks of workstations. This paper presents several operational semantics for a coordination language that supports first-class (shared) distributed data repositories. The computation sub-language considered is an untyped call-by-value functional language similar to pure scheme. The first semantics describes a conventional synchronous message-passing implementation; the second is a formulation of a CmPS implementation; and, the third refines this implementation to support computation migration, a technique to lazily migrate control state. Using computation migration, an implementation “distributes” a continuation among multiple machines reducing bandwidth requirements needed to support thread mobility. We prove the equivalence of all three systems and describe optimizations and implementation issues that arise from using a CmPS-driven coordination language.

The major design challenge to realize intelligent home network services is organizing distributed and heterogeneous home devices effectively. In order to meet the design challenge, an agent space based multi-agent architecture is considered. In addition, we also proposed a new middleware on the IEEE1394 network to support reliable communication between agent spaces.

It is fairly accepted that the realization of complex systems must be accomplished step by step from the initial specification, through a sequence of intermediate phases, to the final program. These development steps, linking a preliminary version, or description, of the program to a more detailed one, are usually called refinement steps, while the intermediate stages of a refinement process are called levels of abstraction.A refinement calculus is a means to support this modus operandi in program development, allowing linking different levels of abstraction; it introduces a precise relation between intermediate descriptions, and the rules to check whether the relation is satisfied.Tuple space languages are concurrent languages, that foster the definition of autonomous entities of computation (the processes), and offer mechanisms for their synchronization and communication. In particular, they represent one of the most acknowledged models of coordination. Tuple space languages are based on the idea that a dynamic collection of tuples can act as shared state of concurrent processes, and play the role of coordination media among them.To build a refinement calculus for tuple spaces, we address three points, in this paper: 1.(1) We single out a specification language, a variation of first-order temporal logic. Temporal relations between propositional formulae are not expressive enough to describe relations between tuple spaces, which are multisets of atoms. The specification language, called Oikostl, includes three new temporal operators that enhance the expressive power of the logic, permitting to directly link state transitions and state configurations. The semantics of the specification language is formally defined, and a set of useful properties for refinement are shown.2.(2) We introduce a reference language for tuple spaces, dubbed TuSpReL, and define its axiomatic and operational semantics. We need the former to derive properties, the latter to describe the allowed computations of a system. We relate these descriptions, and guarantee that using the axiomatic semantics we can derive properties, which are correct and complete with respect to the operational behavior. The non-deterministic features of tuple space languages make this result new, and more complex than in other programming paradigms. One of the contributions of our work is the idea to derive weakest preconditions exploiting the demonic strict choice in non-deterministic selection. The transition system defining the operational semantics is based on the new notion of enabling precondition, which exploits the angelic strict choice.3.(3) To build the refinement calculus, we take a compositional approach. We first consider the basic statements of the language, and say under which conditions they satisfy a property, then compose these proofs to derive that a system refines a specification. Finally, in the refinement calculus definition, we extend to tuple space languages the ability to exploit logic formulae to specify the behavior of unrefined modules: in the intermediate steps, a system is only partially written in the programming language, and the still unrefined features are described by logical formulae.

Many real-life problems are inherently distributed. The applications may be spatially distributed, such as interpreting and integrating data from spatially distributed sources. It is also possible to have the applications being functionally distributed, such as bringing together a number of specialized medical-diagnosis systems on a particularly difficult case. In addition, the applications might be temporally distributed, as in a factory where the production line consists of several work areas, each having an expert system responsible for scheduling orders. Research in cooperating intelligent systems has led to the development of many computational models ( Huhns and Singh, 1992 , Hewitt, 1991 , Gasser, 1991 , Polat et al., 1993 , Polat and Guvenir, 1993 , Polat and Guvenir, 1994 , Shoham, 1993 Sycara, 1989 ) for coordinating several intelligent systems for solving complex problems involving diverse knowledge and activity. In this paper, a system for coordinating problem solving activities of multiple intelligent agents using the tuple space model of computation is described. The tuple space based problem solving framework is implemented on an Intel Hypercube iPSC/2 allowing multiple rule-based systems performing their dedicated tasks in parallel. The tasks are interrelated, in other words, there exists a partial order among the tasks which have to be performed.

BaLinda K implements objects in a functional framework. Active objects, which permit concurrent execution and tuple exchanges between externally invoked methods and the object body within the confines of an object boundary, are shown to be a useful tool for establishing concurrency relations between parallel tasks.

Large-scale distributed systems often require complex interaction among dynamically joining and leaving participants. Compared to classical approaches coordinated by a central authority, peer-to-peer systems have been shown to provide a highly scalable and flexible architecture for such scenarios. Coordination middleware like tuple spaces can help to unburden developers from coping with the complexity of distributed coordination by offering simple abstractions for the decoupled interaction of autonomous peers. However, a fault-tolerant peer-to-peer system can only be built if replication mechanisms exist to persist data on several peers at once. To enrich space-based middleware with a flexible replication mechanism, we have designed a generic, plugin-based replication framework that supports easy adaptation via configurable replication schemes. The framework may act as a testbed to analyze the efficiency and reliability of different replication strategies. Its architecture is built via highly composable coordination patterns that internally interact via space containers. Using the generic framework, this paper shows how different variants of multi-master replication can be realized and how they can be adapted for various scenarios.

SAPERE (“Self-aware Pervasive Service Ecosystems”) is a general framework to support the decentralized execution of self-organizing pervasive computing services. In this paper, we present the rationale underlying SAPERE and its reference conceptual architecture. Following, we sketch the middleware infrastructure of SAPERE and detail the interaction model implemented by it, based on a limited set of “eco-laws”. Finally, we show how in SAPERE one can express general-purpose distributed self-organizing schemes.