Search

Software switches are being deployed in SDN to enable a wide spectrum of non-traditional applications. The popular Open vSwitch uses a variant of Tuple Space Search (TSS) for packet classifications. Although it has good performance on rule updates, it is less efficient than decision trees on lookups. In this paper, we propose a two-stage framework consisting of heterogeneous algorithms to adaptively exploit different characteristics of the rule sets at different scales. In the first stage, partial decision trees are constructed from several rule subsets grouped with respect to their small fields . This grouping eliminates rule replications at large scales, thereby enabling very efficient pre-cuttings. The second stage handles packet classification at small scales for non-leaf terminal nodes , where rule replications within each subspace may lead to inefficient cuttings. A salient fact is that small space means long address prefixes or less nesting levels of ranges, both indicating a very limited tuple space. To exploit this favorable property, we employ a TSS-based algorithm for these subsets following tree constructions. Experimental results show that our work has comparable update performance to TSS in Open vSwitch, while achieving almost an order-of-magnitude improvement on classification performance over TSS.

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.

We review some results regarding specification, programming and verification of different classes of distributed systems which stemmed from the research of the Concurrency and Mobility Group at University of Firenze. More specifically, we examine the distinguishing features of network-aware programming, service-oriented computing, autonomic computing, and collective adaptive systems programming. We then present an overview of four different languages, namely Klaim, Cows, Scel and AbC. For each language, we discuss design choices, present syntax and semantics, show how the different formalisms can be used to model and program a travel booking scenario, and describe programming environments and verification techniques., In Press

Packet classification provides a way to discriminate packets and enables many differentiated functionalities. In this chapter, we present how packet classification is accomplished by expressing rules in a classfier. We list the key performance requirements of a packet classification algorithm as the number of memory accesses it needs and the amount of storage it occupies. We then present a number of algorithms that are extensions of trie based algorithms used for IP address lookup. We also outline various approaches for classifying a packet in an arbitrary number of dimensions: divide and conquer, cross-producting, tuple space, and decision tree. We then describe algorithms using each approach. Finally, we conclude the chapter with a discussion of hardware solutions using TCAMs.

Conceptually, tuple spaces are shared memory objects that provide operations to store and retrieve ordered sets of data, called tuples. Tuples stored in a tuple space are accessed by the contents of their fields, working as an associative memory. Although there are some proposals for secure tuple spaces, accessing tuples through field contents makes these systems susceptible to attacks that could impair user and data privacy, since servers must access tuple data. In order to deal with these limitations and provide privacy in the tuple space model, this paper proposes some extensions to DepSpace, a tuple space system that implements dependability and security properties through a set of mechanisms that are not enough to ensure privacy. The resulting system provides privacy and, at the same time, allows tuple selection/matches similar to the traditional insecure model, i.e., it does not constraint the matching possibilities. The main problem to be addressed is that servers must select tuples based on their contents without knowing them. The proposed solution uses robust cryptographic schemes, as order-preserving encryption and homomorphic encryption, to provide this functionality without revealing the tuple contents. An analysis concerning security aspects of DepSpace is presented, as well as the benefits of the proposed solutions. A set of experiments, executed with an implementation of the proposed protocols, shows the feasibility of the proposed solutions and shed some light on both the behavior of the system and the costs to provide privacy in the tuple spaces model.

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.

Packet classification is one of the main core functions of networking. With the advent of Software-Defined Networking, packet classification has become more challenging by introducing many-field rulesets. In this paper, we propose an algorithm, Clustering-Based Packet Classification (CBPC), which divides ruleset into some clusters using a new hybrid clustering method, based on an innovative bit-level view. Those rules that have more common wildcard and non-wildcard bit positions are put into the same cluster. Each cluster uses common non-wildcard positions of its rules to produce keys for a hash table insertion and query stages. This makes possible to use hash tables without involving difficulties with inserting and querying ternary vectors, because our algorithm converts it to simple binary operations. In fact, we ignore a portion of information of the rules in key production for the hash tables. It overcomes the problem of extending wildcards to all of the possible values. It is true that some information is lost but it is covered by full matching at the hash table entries. We propose two versions for CBPC, online and offline. The online version supports update, which is an important requirement for today's packet classification algorithms. The proposed algorithm is evaluated and compared with some well-known and state-of-the-art algorithms by extensive simulations. The results show that Online-CBPC achieves 197% higher throughput and 64% faster update than Tuple Space Search, OpenVSwitch standard algorithm, while using almost the same amount of memory.

The tuple space abstraction provides an easy-to-use programming paradigm for distributed applications. Intuitively, it behaves like a distributed shared memory, where applications write and read entries (tuples). When deployed over a wide area network, the tuple space needs to efficiently cope with faults of links and nodes. Erasure coding techniques are increasingly popular to deal with such catastrophic events, in particular due to their storage efficiency with respect to replication. When a client writes a tuple into the system, this is first striped into k blocks and encoded into \(n > k\) blocks, in a fault-redundant manner. Then, any k out of the n blocks are sufficient to reconstruct and read the tuple. This paper presents several strategies to place those blocks across the set of nodes of a wide area network, that all together form the tuple space. We present the performance trade-offs of different placement strategies by means of simulations and a Python implementation of a distributed tuple space. Our results reveal important differences in the efficiency of the different strategies, for example in terms of block fetching latency, and that having some knowledge of the underlying network graph topology is highly beneficial.

Open distributed systems are typically composed by an unknown number of processes running in heterogeneous hosts. Their communication often requires tolerance to temporary disconnections and security against malicious actions. Tuple spaces are a well-known coordination model for this kind of systems. They can support communication that is decoupled both in time and space. There are currently several implementations of distributed fault-tolerant tuple spaces but they are not Byzantine-resilient, i.e., they do not provide a correct service if some replicas are attacked and start to misbehave. This paper presents an efficient implementation of a linearizable Byzantine fault-tolerant Tuple Space (LBTS) that uses a novel Byzantine quorum systems replication technique in which most operations are implemented by quorum protocols while stronger operations are implemented by more expensive protocols based on consensus. LBTS is linearizable and wait-free, showing interesting performance gains when compared to a similar construction based on state machine replication.

In systems coordinated with a distributed set of tuple spaces, it is crucial to make agents easily retrieving the tuples they are interested in. This can be achieved by some sorting technique that can 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 col lective sort problem for distributed tuple spaces, where an on-line, background service of autonomous agents is in charge of moving tuples from one space to the other until reaching complete sorting, 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-organising solution inspired by ants' brood sorting. This is based on simple agents that perform partial observations and accordingly take decisions on tuple movement. Complete convergence from any initial configuration of tuples is addressed by a form of fully-adaptive simulated annealing, based on noise tuples inserted and removed by agents on a by-need basis so as to avoid situations of non-optimal sorting. The approach is evaluated by stochastic simulations, which provide evidence of full-sorting emergence, scalability, and reactiveness to external interactions.

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.

International audience; This chapter presents the JaCaMo framework for Social Coordination. JaCaMo is a development and execution platform that provides programming constructs that match the abstractions used at the levels of a multi-agent system for expressing social coordination. More precisely, JaCaMo defines a uniform and consistent programming model seamlessly integrating concepts from programming dimensions developed within separate communities in the Multi-Agent research domain: 1) agents, 2) environment, 3) interaction languages and protocols, and 4) multi-agent organisations and norms. The applications and example presented in this chapter show the added value of this seamless integration of each dimension for the development of complex and distributed applications.

In this chapter a novel approach to coordination in self-organising systems is described, which rethinks the basis of chemically inspired coordination, from both the engineering standpoint of coordination laws and primitives design, and from the scientific standpoint of relative linguistic expressiveness. Accordingly, first of all state of art literature regarding nature-inspired coordination is reviewed (Sects. 3.1 and 3.2), then the well-known local versus global issue in self-organising systems is dealt with by engineering coordination laws as artificial chemical reactions with custom kinetic rates (Sect. 3.3). After this, the impact of uniform coordination primitives on self-organising systems is discussed, experiments on their applicability are reported, and their formal semantics is defined (Sect. 3.4).

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.

Linguistic primitives for replica-aware coordination offer suitable solutions to the challenging problems of data distribution and locality in large-scale high-performance computing. The data replication mechanisms that had previously been designed to extend Klaim with replicated tuples are now used to experiment with X10, a parallel programming language primarily targeting clusters of multi-core processors linked in a large-scale system via high-performance networks. Our approach aims at allowing the programmer to specify and coordinate the replication of shared data items by taking into account the desired consistency properties. The programmer can hence exploit such flexible mechanisms to adapt data distribution and locality to the needs of the application, in order to improve performance in terms of concurrency and data access. We investigate issues related to replica consistency and provide a performance analysis, which includes scenarios where replica-based specifications and relaxed consistency provide significant performance gains.

One way for improving the tuple space search-based table lookup in the software system (e.g., flow matching process of Open vSwitch) is to reduce the number of tuple spaces to be examined. For this purpose, we discuss two approaches based on space-efficient data structures, Bloom filter and simTable proposed in this paper. Click-based experiments show that Bloom filter and simTable noticeably reduce the number of tuple spaces to be examined (i.e., the number of tuple spaces to be examined is 1 in most cases even with 121 tuple spaces). However, two approaches show different results in terms of the table lookup time. Bloom filter without hardware parallelism causes noticeable processing overhead that is heavily affected by the number of tuple spaces while simTable causes low processing overhead regardless of the number of tuple spaces. As a result, the use of Bloom filter/simTable increases/reduces the table lookup time compared to the original tuple space search-based table lookup (e.g., from 1917ns to 5032ns/432ns in case of 25 tuple spaces).

Multidimensional packet classification has attracted considerable research interests in the past few years due to the increasing demand on policy based packet forwarding and security services. These network services typically involve determining the action to take on packets according to a set of rules. As the number of rules increases, time for determining the best matched rule for an incoming IP packet will increase and subsequently incur long processing delay. To address this issue, in this paper we propose a two-dimensional packet classification algorithm which focuses on reducing time for classification while keeping reasonable memory requirement in practice. Our approach extends the tuple space framework and then allows performing binary search on the tuple space. To our knowledge, the proposed scheme is the first binary search scheme on two-dimensional tuples. With the proposed scheme, given a filter set with n two-dimensional filters, it requires only O(log(w)) hash operations to determine the best matched filter, where w is the maximum prefix length of filters. The proposed scheme achieves fast packet classification, and according to our experimental results, it does not require huge memory space. This makes it useful for network applications that require high speed packet classification.

While large-scale parallel/distributed simulations are rapidly becoming critical research modalities in academia and industry, their efficient and scalable implementations continue to present many challenges. A key challenge is that the dynamic and complex communication/coordination required by these applications (dependent on the state of the phenomenon being modeled) are determined by the specific numerical formulation, the domain decomposition and/or sub-domain refinement algorithms used, etc. and are known only at runtime. This paper presents Seine, a dynamic geometry-based shared-space interaction framework for scientific applications. The framework provides the flexibility of shared-space-based models and supports extremely dynamic communication/coordination patterns, while still enabling scalable implementations. The design and prototype implementation of Seine are presented. Seine complements and can be used in conjunction with existing parallel programming systems such as MPI and OpenMP. An experimental evaluation using an adaptive multi-block oil-reservoir simulation is used to demonstrate the performance and scalability of applications using Seine. Copyright © 2006 John Wiley & Sons, Ltd.

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.

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 initiate an investigation about security problems which occur when exploiting a Linda-like data driven coordination model in an open environment. In this scenario, there is no guarantee that all the agents accessing the shared tuple space are trusted. Starting from the analysis of the few proposals already available in the literature, we present a novel coordination model which provides mechanisms to manage tuple access control. The first mechanism supports logical partitions of the shared repository: in this way we can restrict the access to tuples inside a partition, simply by limiting the access to the partition itself. The second mechanism consists of adding to the tuples some extra information which exploit asymmetric cryptography in order, e.g., to authenticate the producer of a tuple or to identify its reader/consumer. Finally, we support the possibility to define access control policies based on the kind of operations an agent performs on a tuple, thus discriminating between (destructive) input and (non-destructive) read operations.

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.

Some of the most peculiar traits of socio-technical KIE (knowledge-intensive environments) – such as unpredictability of agents’ behaviour, ever-growing amount of information to manage, fast-paced production/consumption – tangle coordination of information, by affecting, e.g., reachability by knowledge prosumers and manageability by the IT infrastructure. Here, we propose a novel approach to coordination in KIE, by extending the \({MoK}\) model for knowledge self-organisation with key concepts from the cognitive theory of BIC (behavioural implicit communication).

Coordination is essential for dynamic distributed systems exhibiting autonomous behaviors. Spatially distributed, locally interacting, propagating computational fields are particularly appealing for allowing components to join and leave with little or no overhead. In our approach, the space topology is represented by a graph-shaped field, namely a network with attributes on both nodes and arcs, where arcs represent interaction capabilities between nodes. We propose a calculus where computation is strictly synchronous and corresponds to sequential computations of fixpoints in the graph-shaped field. Under some conditions, those fixpoints can be computed by synchronised iterations, where in each iteration the attributes of a node is updated based on the attributes of the neighbours in the previous iteration. Basic constructs are reminiscent of the semiring μ-calculus, a semiring-valued generalisation of the modal μ-calculus, which provides a flexible mechanism to specify the neighbourhood range (according to path formulae) and the way attributes should be combined (through semiring operators). Additional control-flow constructs allow one to conveniently structure the fixpoint computations. We illustrate our approach with a case study based on a disaster recovery scenario, implemented in a prototype simulator that we use to evaluate the performance of a disaster recovery strategy.

We present the tuple-based coordination language RepliKlaim, which enriches Klaim with primitives for replica-aware coordination. Our overall goal is to offer suitable solutions to the challenging problems of data distribution and locality in large-scale high performance computing. In particular, RepliKlaim allows the programmer to specify and coordinate the replication of shared data items and the desired consistency properties. The programmer can hence exploit such flexible mechanisms to adapt data distribution and locality to the needs of the application, so to improve performance in terms of concurrency and data access. We investigate issues related to replica consistency, provide an operational semantics that guides the implementation of the language, and discuss the main synchronization mechanisms of our prototypical run-time framework. Finally, we provide a performance analysis, which includes scenarios where replica-based specifications and relaxed consistency provide significant performance gains.

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.

SAPERE is a general multiagent framework to support the development of self-organizing pervasive computing services. One of the key aspects of the SAPERE approach is to have all interactions between agents take place in an indirect way, via a shared spatial environment. In such environment, a set of nature-inspired coordination laws have been defined to rule the coordination activities of the application agents and promote the provisioning of adaptive and self-organizing services.

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.

The knowledge reuse and fusion/transformation (KRAFT) project has defined a generic agent-based architecture to support knowledge fusion — the process of locating and extracting knowledge from multiple, heterogeneous on-line sources, and transforming it so that the union of the knowledge can be applied in problem-solving. KRAFT focuses on knowledge in the form of constraints expressed against an object data model defined by a shared ontology. KRAFT employs three kinds of agent: facilitators locate appropriate on-line sources of knowledge; wrappers transform heterogeneous knowledge to a homogeneous constraint interchange format; mediators fuse the constraints together with associated data to form a dynamically-composed constraint satisfaction problem, which is then passed to an existing constraint solver engine to compute solutions. The KRAFT architecture has been designed to be scalable to large numbers of agents; this paper describes the features of the architecture designed to support scalability. In particular, we examine static techniques that underpin the growth of large-scale KRAFT networks, and dynamic techniques that allow reorganisation of a KRAFT network as it increases in scale.

We develop an action systems-based approach that supports the separation of the design of the functional or computation aspects of a system under construction from the coordination and synchronization issues. The computation aspects are modeled as nondeterministic actions that work in parallel with the coordination actions, which impose some control on the nondeterministic part. We define a special form of action systems that models this type of coordination activity. Certain forms of real-time scheduling and coordination as well as exception handling are shown to be special cases of our approach. We show how the coordinators can be stepwise brought about from a high-level specification of the target system and how the reasoning about their behaviors is carried out separately from the computation aspects of the system within the refinement calculus.

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.

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.

We give an overview of recent results and work in progress on deterministic negotiations, a concurrency model with atomic multi-party negotiations as primitive actions.

This paper presents EvoSpace, a Cloud service for the development of distributed evolutionary algorithms. EvoSpace is based on the tuple space model, an associatively addressed memory space shared by several processes. Remote clients, called EvoWorkers, connect to EvoSpace and periodically take a subset of individuals from the global population, perform evolutionary operations on them, and return a set of new individuals. Several EvoWorkers carry out the evolutionary search in parallel and asynchronously, interacting with each other through the central repository. EvoSpace is designed to be domain independent and flexible, in the sense that in can be used with different types of evolutionary algorithms and applications. In this paper, a genetic algorithm is tested on the EvoSpace platform using a well-known benchmark problem, achieving promising results compared to a standard evolutionary system.

We advocate the role of tuple-based coordination languages as effective tools for event-driven programming of situated multi-agent systems (MAS). By focussing on logic-based coordination artefacts, we discuss the benefits of exploiting ReSpecT tuple centres as event-driven abstractions for MAS coordination.

Today’s developers often face the demanding task of developing software for ensembles: systems with massive numbers of nodes, operating in open and non-deterministic environments with complex interactions, and the need to dynamically adapt to new requirements, technologies or environmental conditions without redeployment and without interruption of the system’s functionality. Conventional development approaches and languages do not provide adequate support for the problems posed by this challenge. The goal of the ASCENS project is to develop a coherent, integrated set of methods and tools to build software for ensembles. To this end we research foundational issues that arise during the development of these kinds of systems, and we build mathematical models that address them. Based on these theories we design a family of languages for engineering ensembles, formal methods that can handle the size, complexity and adaptivity required by ensembles, and software-development methods that provide guidance for developers. In this paper we provide an overview of several research areas of ASCENS: the SOTA approach to ensemble engineering and the underlying formal model called GEM, formal notions of adaptation and awareness, the SCEL language, quantitative analysis of ensembles, and finally software-engineering methods for ensembles.

Tuple Space based Mobile Middleware (TSMM), with tuple space as its coordination medium, provides multiple decoupled behaviors for coordinating interactions between different agents of supported applications. However, maintaining consistency in TSMM is a challenging problem, considering its underlying infrastructure with unpredictable host mobility, sporadic network dynamics, and unreliability in communication links. Existing TSMM maintains consistency by coupling interacting agents, which in turn reduces decoupling abilities of TSMM, thereby restricting development of robust and flexible applications. This paper addresses consistency problems while decoupling agent interactions in TSMM, which renders complete decoupling of interactions. It proposes mechanisms to resolve consistency problems in a fully-decoupled TSMM. Both OUT-consistency and IN-consistency problems are handled in proposed mechanisms. This paper also suggests an approach for formalizing proposed consistency mechanisms in TSMM in order to appropriately analyze reliability and robustness of TSMM as coordination platform for mobile applications. Formalization is carried out using Mobile UNITY.

The next generation of computational systems is going to mix up pervasive scenarios with cloud computing, with both intelligent and non-intelligent agents working as the reference component abstractions. A uniform set of MAS abstractions expressive enough to deal with both embodied and disembodied computation is required, in particular when dealing with the complexity of interaction. Along this line, in this paper we define an event-driven coordination architecture, along with a coherent event model, and test it upon the TuCSoN model and technology for MAS coordination.

Linda, a general purpose coordination language, has been used to make a language parallel. Based on a logically shared tuplespace, Linda poses difficulties to be efficiently implemented on a distributed multiprocessor system. This paper reports our approach to solve the problem: processors are divided into groups, and each group has a group manager to provide a local view of the global tuplespace, and handles the tuplespace operations incurred by processors within the group. To maintain the consistency and correctness of the Linda tuplespace operations, we propose the algorithms of a group manager. We also implement the algorithms on a transputer-based multicomputer and show the experiment results.

Tuple space model is a simple and efficient data-driven coordination model, suitable for different mobile middleware platforms. A significant performance factor of this model is tuple space structure. Existing tuple space models have sequential tuple space structure, which works efficiently with tuple-producing primitives. But, tuple-reading and -consuming primitives that drive overall performance of tuple space model, generate substantial overhead with this sequential structure. In this paper, we propose an efficient tuple space structure, which is not only simple, but also improves performance and scalability of tuple space model. We have compared proposed structure with existing ones to show the improvements. Tuple space model with proposed tuple space structure not only preserves the ease of developing mobile applications, but also facilitates performance gain during their execution.

From the point of view of multiparadigm distributed programming one of the most interesting communication mechanisms is associative communication based on a shared dataspace, as exemplified in the Linda coordination language. In fact, Linda has been used as coordination layer to parallelize several sequential programming languages, like 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 effectively uses the network version of Linda''s tuple space.

To support and engineer the spatial coordination of distributed pervasive services, we propose a chemical-inspired model, which extends tuple spaces with the ability of evolving tuples mimicking chemical systems, that is, in terms of reaction and diffusion rules that apply to tuples modulo semantic match. The suitability of this model is studied by considering a self-adaptive display infrastructure providing people nearby with several visualization services (advertisements, news, personal and social content). The key result of this article is that general-purpose chemical reactions inspired by population dynamics can be used in pervasive applications to enact spatial computing patterns of competition and gradient-based interaction.

In this paper, we discuss the most recent coordination extension to the PicOS-tuples environment, inspired, to a degree, by B-Threads and FACTS. We illustrate the extensions with two design patterns, highly useful in WSN computations, known as regulative superimposition and distributed detection. Those patterns are employed in a debugging protocol that retrieves snapshots of node states. We demonstrate how our new idioms can be propitious for separating concerns in WSN programming using tuples.

This paper studies a behavioural theory of the π-calculus with session types under the fundamental principles of the practice of distributed computing — asynchronous communication which is order-preserving inside each connection (session), augmented with asynchronous inspection of events (message arrivals). A new theory of bisimulations is introduced, distinct from either standard\ud asynchronous or synchronous bisimilarity, accurately capturing the semantic nature of session-based asynchronously communicating processes augmented with\ud event primitives. The bisimilarity coincides with the reduction-closed barbed congruence. We examine its properties and compare them with existing semantics.\ud Using the behavioural theory, we verify that the program transformation of multithreaded into event-driven session based processes, using Lauer-Needham duality,\ud is type and semantic preserving.