Solving the Linda multiple rd problem using the copy-collect primitive

Antony I. T. Rowstron, Alan Wood

Research output: Contribution to journalArticlepeer-review


Linda is a mature co-ordination language that has been in use for several years. However, as a result of recent work on the model we have found a simple class of operation that is widely used in many different algorithms which the Linda model is unable to express in a viable fashion. An example algorithm which uses this operation is the composition of two binary relations. By examining how to implement this in parallel using Linda we demonstrate that the approaches possible using the current Linda primitives are unsatisfactory. This paper demonstrates how this "multiple rd problem" can be overcome by the addition of a primitive to the Linda model, copy-collect. This builds on previous work on another primitive called collect (Butcher et al., 1994). The parallel composition of two binary relations using the copy-collect primitive can be achieved with maximal parallelism. (C) 1998 Elsevier Science B.V. All rights reserved.

Original languageEnglish
Pages (from-to)335-358
Number of pages24
JournalScience of Computer Programming
Issue number2-3
Publication statusPublished - Jul 1998


  • Linda
  • co-ordination models
  • multiple rd problem

Cite this