Search

The authors briefly outline the Linda tuple space model and then comment on current work. This includes recent experiments involving Linda programs on a 64-node hypercube, the development of an improved version of C-Linda, and research which will culminate in a multiple tuple space system. >

A distributed implementation of a parallel system is of interest because it can provide an economical source of concurrency, can be scaled easily to match the needs of particular computations, and can be fault-tolerant. A design is described for such an implementation for the Linda parallel programming system, in which processes share a memory called the tuple space. Fault tolerance is achieved by replication: by having more than one copy of the tuple space, some replicas can provide information when others are not accessible due to failures. The replication technique takes advantage of the semantics of Linda so that processes encounter little delay in accessing the tuple space. In addition to providing an efficient implementation for Linda, the study extends work on replication techniques by showing what can be done when semantics are taken into account. >

Replication is a common method for increasing the availability of data in a distributed environment. The authors' interest is in the application of replication techniques in the domain of parallel processing. They explore the issues concerning degree of replication and granularity in the context of a distributed and highly available Linda tuple space. In particular, they study the performance effects of varying the number of replicas and the granularities of replication and concurrency control. Traditionally, when using replication in databases, the granularity of replication and that of concurrency control have been the same (at the file level (D.K. Gifford, 1979), for example). This is not an inherent requirement however. The authors show by detailed simulation of a replicated Linda tuple space that it is useful to separate the two granularities and that it is an important design issue especially in parallel processing systems. >

Nowadays, autonomous vehicles are undergoing a distinct evolution, taking advantage of the recent technological progress in computer architectures. The development tools are more sophisticated, forwarding the trend to dedicated architectures. In the paper, the authors consider a parallel vision sub-system integrated in an overall architecture for a mobile robot (indoor autonomous vehicle). The system modules work in parallel, communicating through a hierarchical blackboard, an extension of the 'tuple space' from LINDA concepts, where they may exchange data or synchronization messages. The processing elements are of different skills, built around 50 MHz i860-XP Intel RISC processors for high level processing, and pipelined systolic array processors based on PLAs or FPGAs for low level image processing. >

Distributed systems have many advantages over centralized systems. The authors focus on the novel Linda Tuple Space (TS) model designed for generative coordination in a distributed shared memory model. Currently, the object-oriented programming (OOP) model is considered a most suitable model for handling complex computer-based systems. Among the OOP languages, the C++ language is a de-facto standard for developing advanced systems. The paper takes these two orthogonal computational models and combines them in a new way to form a C++/Linda model that supports transparent distributed objects. The idea is to create an integrated model that builds on the advantages of both models while complementing whatever is missing in each one alone. A prototype of the C++/Linda model was implemented and several distributed programs were successfully run on it.

Introduces a software package called "Glenda", designed to support easy parallel programming. Glenda implements a coordination language based on a global "tuple space". This coordination language consists of seven operations to output and input tuples from within participating programs. Glenda communications are performed using PVM (Parallel Virtual Machine) message passing functions. The Glenda package consists of a preprocessor to add the coordination operations to the C programming language, a set of communication functions and a tuple server process. We show the utility of Glenda based on an underwater acoustic modeling benchmark. >

A mechanism is presented for a fault-tolerant tuple space. By augmenting the MOM model of fault tolerance, a LINDA-style system is proposed that supports failure and recovery of worker processes and tuple-space in any state. System tuple space is replicated using local tuple-space segments. Each local tuple space replicates tuples and states produced or processed by local workers. All tuple requests are handled through local tuple-space agents prior to being forwarded to a system tuple-space manager in order to update tuple states. A MOM extension to LINDA operators allows local managers to know when tuple states can be committed. In the event of a local tuple-space failure, the local tuple-space segment is reconstructed from system tuples and states associated with the failed local node. The reconstructed local tuple space is inherited by another local tuple-space. For a system tuple-space failure, system tuple space is reconstructed by interrogating local tuple space managers. Tuple replicas and states are maintained with minimal system message overhead during nonfailure operation.

Robust parallel computation in Linda requires both tuple space and processes to be resilient to failure. In this paper, we present PLinda 2.0, set of extensions to Linda to support robust parallel computation on loosely coupled processors communicating over a network. The principal extensions of PLinda 2.0 to Linda are transaction mechanisms for reliable tuple space and process-private logging mechanisms for resilient processes. The transaction mechanisms support two kinds of tuple space: stable tuple space always guaranteed to reflect state as of last committed transaction, and unstable tuple space protected by a transaction-consistent checkpoint. The process-private logging mechanisms are provided as tools for a process checkpointing scheme. These mechanisms allow the customization of checkpointing and recovery operations in each process to achieve low runtime overhead. >

We introduce the design of a parallel library for MPI based on the Linda programming paradigm, called Eilean. It provides a scalable distribution of the tuple space through a hierarchical (or cluster) partitioning scheme, and tuple type specific access/distribution policies. Portability of the library is achieved using the message passing standard MPI as the underlying communication system. The hierarchical distribution provides a static, yet general partition of the tuple space through the available processors. With such general structure, the run-time system, aided by programmer hints, can map tuples closely to the processes which use them. To accomplish the tuple mapping task, Eilean treats tuples differently according to their use within the application. The required information about tuple access patterns is explicitly given by the programmer and used during run-time. >

A simple technique for making distributed programs that are based on the bag-of-tasks programming paradigm, in which the problem space is divided up and parceled out to processes as independent subtasks, fault tolerant is presented. The technique is based on adding a conditional swap operator to Linda, a system for programming distributed applications whose most notable feature is an associative memory called tuple space. The way in which this new operator is used to achieve fault-tolerance in programs is described and illustrated by a simple program for DNA sequencing. Extensions for dynamic subtask creation are described. A straightforward way to implement the atomic swap operator within an existing fault-tolerant version of Linda is also presented. >

Tuple Space provides primitives convenient for description of data-sharing and interprocess communication, but its implementation on distributed systems is less efficient than that on shared memory machines. Multiprotocol Tuple Space improves the implementation on distributed systems. That provides three replication-consistency protocols that are weakened to different degrees. By selecting these protocols according to communication patterns, communication through Tuple Space can be optimized. >

Proposes an extension to the authors' current C* programming environment that allows a programmer to connect multiple data-parallel modules with each other and with parallel I/O devices. The interface is based upon the Linda concept of multiple asynchronous processes interacting through tuple space. The resulting programs can be seen as single instruction stream, multiple data stream (SIMD) within each module and multiple instruction stream, multiple data stream (MIMD) between modules. Programs can run with a high level of efficiency, because the purpose of the Linda calls is to facilitate the relatively infrequent interactions between modules. >

A notation for describing parallel evaluation of functional expressions is presented. The notation is an extension of a functional language by the LINDA concept. This concept introduces the notion of process and communication between processes by means of a so-called tuple space. The notation strictly distinguishes between processes which map tuple spaces to tuple spaces and pure functions defined on data domains. The referential transparency of functional expressions is preserved by a notation and an operational semantics which separates the level on which processes are expressed from the level on which functions on data domains are described. >

Research in the area of fault-tolerant distributed systems has focused to a large extent on data surviving various forms of failure. However, in environments where cooperation among processes is important the authors argue that high availability of processes, in addition to their recoverability is crucial. Their specific interest is in the Linda tuple space paradigm. They discuss efficient techniques for making Linda processes recoverable and outline some characteristics of Linda that make it particularly suitable for implementing fault-tolerance. They also propose a simple extension to their recoverable process mechanism that makes processes highly available. >

The authors describe BaLinda (Biddle and Linda) Lisp, a parallel execution Lisp dialect designed to take advantage of the architectural capabilities of Biddle (bidirectional data driven Lisp engine). The Future construct is used to initiate parallel execution threads, which may communicate through Linda-like commands operating on a tuple space. These features provide good support for parallel execution, and blend together well with notational consistency and simplicity. Unstructured task initiation and termination commands are avoided, while mandatory and speculative parallelisms (lazy versus eager executions) are both supported. >

We examine the inherent properties of some of the most popular coordination models of today and show how they contribute to the difficulty of systematic construction of coordination protocols for the cooperation of concurrent processes, as explicit, tangible pieces of software. They include the object oriented models of communication and the generative tuple space paradigm of models such as Linda. We then describe a new generic model: Idealized Worker Idealized Manager (IWIM) and discuss its advantages for coordination of concurrent activities, especially in control oriented applications. We demonstrate its "completeness" by showing that it can trivially emulate other well known communication and coordination models. Separation of computation and coordination code into different program modules is one of the important properties of this model, which is fully exploited in the pure coordination language MANIFOLD.

In the last few years the use of distributed structured shared memory paradigms for coordination between parallel processes has become common. One of the most well known implementations of this paradigm is the shared tuple space model (as used in Linda). We describe a new set of primitives for fully distributed coordination of processes and agents using tuple spaces, called the BONITA primitives. The Linda primitives provide synchronous access to tuple spaces, whereas the BONITA primitives provide asynchronous access to tuple spaces. The proposed primitives are able to mimic the Linda primitives, therefore providing the ease of use and expressibility of Linda together with a number of advantages for the coordination of agents or processes in distributed environments. The primitives allow user processes to perform computation concurrently with tuple space accesses, and provide new coordination constructs which lead to more efficient programs. We present the (informal) semantics of the BONITA primitives, a description of how the Linda primitives can be modelled using them and a demonstration of the advantages of the BONITA primitives over the Linda primitives.

The paper proposes and analyses a scalable model of an associative distributed shared memory for massively parallel architectures. The proposed model is hierarchical and fits the modern style of structured parallel programming. If parallel applications are composed of a set of modules with a well-defined scope of interaction, the proposed model can induce a memory access latency time that only logarithmically increases with the number of nodes. Experimental results show the effectiveness of the model with a transputer-based implementation.

Given a shared, atomic read-modify-write register r with deterministic operations, Herlihy (1991) has defined an interference condition on the operations of r and shown that this condition must be satisfied for r to support wait-free consensus. We extend this interference condition to general linearizable shared objects with nondeterministic operations. The extension is applicable to the entire set of objects shared by a parallel programming system, so long as there exists a linearizable implementation of the system. We illustrate this by applying it to Tuple Space, the shared data structure implemented by the Linda coordination language, and show that the standard set of Tuple Space operations cannot support wait-free consensus. This result holds even if the underlying architecture does support consensus, and establishes that previous efforts to construct resilient implementations of Tuple Space are incapable of solving consensus in the face of application-level process failures. Finally, we extend Linda with a new Tuple Space operation that supports consensus, and discuss efficient wait-free and non-wait-free implementations of the new operation and the architectural features required to support them.

We argue that the programming simplicity and message passing complexity of implementing LOTOS multi-rendezvous largely depends on the underlying communication structure. The programming simplicity and low complexity of our algorithm are due to our viewing the multi-rendezvous problem as a distributed mutual exclusion problem. Using the parallel programming environment of Linda, we present an efficient algorithm to easily implement multi-rendezvous in LOTOS. The orthogonal communication structure in Linda allows us to separate synchronization concerns in multi-rendezvous from concerns in interprocess communication in an implementation. The concept, of Table Space in Linda and the associated in, out, and rd primitives for managing the tuple space lead to an elegant programming style for distributed implementation of multi-rendezvous.