ALCOMFT-TR-02-118

J. Gabarr\'o, A. Stewart and M. Clint
Grab and Go Systems: a CPO approach to concurrent web and grid-based computation
Barcelona. Work package 4. May 2002.

Abstract: A useful property of web-based information systems (R. Baeza-Yates, B. Ribeiro-Neto,Modern Information Retrieval, Addison-Wesley, 1989) is the ability to display partial information. For example, a web program can display a sequence of fuzzy images which is extended by the production of improved images as execution of the program proceeds. A sequence of improving approximations to an image can be modelled by the elements of a complete partial order (CPO). CPOs can also be used to model grid-based computations. For example, a coalgorithm is a collection of iterative processes, each with identical functionality, which individually generate a series of improving approximations towards a desired goal. The aim of a coalgorithm is to produce faster convergence than could be achieved by any of its constituent processes separately. Each constituent process has the potential to exchange partial information with its companions so that all may make use of the best information available.

In this paper a non-blocking communication abstraction, based on CPOs, is used to develop a model of iterative web- and grid-based computations. The abstraction is novel in that it may not directly match a send communication in one process with a corresponding receive communication in another; rather, a receive communication is identified with taking the least upper bound of the set of messages available at an input port - this set may be empty, contain exactly one messsage or contain multiple messages. In all cases the receiver does not wait but gathers the best available information and proceeds with its computation. Thus, the abstraction corresponds to a loosely coupled model of distributed computation. The applicability of the model is illustrated by a number of disparate examples of distributed iterative computation.

Postscript file: ALCOMFT-TR-02-118.ps.gz (76 kb).