page 1  (22 pages)
2to next section

Law-Governed Linda Communication Model

Naftaly H. Minsky?
Jerrold Leichter

Department of Computer Science
Rutgers University
New Brunswick, NJ, 08903 USA

March 14, 1994


Linda is a very high level communication model which allows processes to communicate without knowing each others's identities and without having to arrange for a definite rendezvous. Along with the considerable advantages of this high level of abstraction, Linda carries some serious liabilities: it is very unsafe, and is difficult to optimize. We propose to remove the first of these difficulties, and alleviate the second | while preserving the advantages of Linda | by means of the concept of law-governed architecture previously applied to centralized and message passing systems. We define a model for Law-Governed Linda (LGL) communication, and we demonstrate its efficacy by means of several illustrative examples.

1 Introduction

There is much which is attractive about the Linda communication model [Gel85], under which processes communicate by placing tuples in a shared and wide open tuple space, and by retrieving tuples from this space. The model uncouples communicating processes in both time and space [BA90] by allowing them to communicate without knowing each others's identities and without having to arrange for a definite rendezvous; it uses a single mechanism for both communication and synchronization; and it lends itself to various styles of communications, including message passing and broadcasting.

But the very generality of this model, and its high level of abstraction, carry with it some serious liabilities. First, Linda communication is unsafe, as unsafe as a market place in which all goods are dumped into the public square, free for anybody to grab as he sees fit. Second, Linda communication is very hard to implement efficiently, because of the lack of any a priori knowledge about who might store which tuples in the shared tuple space, and who might retrieve these tuples.

?Work supported in part by NSF grants No. CCR-8807803 and No. CCR-9308773