Citation

 Segall, E. J. "Tuple Space Operations: Multiple-Key Search, On-Line Matching and Wait-Free Synchronization," Ph.D. Dissertation, Department of Electrical and Computer Engineering, Rutgers University, October 1993.

Abstract

We present new analytic, experimental, and developmental results for the Linda parallel programming language and its Tuple Space paradigm of communication and coordination. This work was motivated by our efforts to use Linda to develop a computational laboratory based on heterogeneous computing elements. New results include algorithmic matching speedup, increased matching parallelism, and positive and negative results regarding Linda's synchronization power.

Our analytical results include a new implementation technique for Tuple Space operations, called Multiple-Key Search (MKS), that is related to prior solutions to the partial match retrieval problem from database systems. We give MKS-based tuple matching algorithms for shared-memory and distributed-memory parallel environments, analyze their off-line and on-line complexity, and show that in the worst case (under certain realistic assumptions) MKS takes an optimal number of operations to find a match, and that one on-line version of MKS is competitive with the off-line version. This is a substantial improvement over current single-key search (SKS) algorithms.

Significantly, MKS removes a performance bottleneck (called a hybrid set) from some Linda programs, and thereby enlarges the class of Linda programs that can execute efficiently. We provide experimental evidence that MKS is substantially faster than SKS in many cases, especially for programs that contain hybrid sets.

As a proof of concept, we developed an MKS based implementation of Linda in Smalltalk-80. To the best of our knowledge, this is the first Linda implementation that performs on-line optimization of tuple space operations. This should help to pave the way for future persistent, distributed, on-line optimized Linda implementations, which, for example, would make Tuple Space a viable paradigm for coordinating a computational laboratory.

In the course of this work, we discovered that it is impossible to implement the Tuple Space equivalent of an atomic Compare-and-Swap operation. This precludes the implementation of a large class of resilient synchronization protocols. We prove this, and show that a new Tuple Space operator, Conditional Atomic Swap (CAS), makes it possible for Linda to solve wait-free consensus, as well as a wide range of resilient protocols.

Sections