Browse Prior Art Database

McCarthy's Amb Cannot Implement Fair Merge Disclosure Number: IPCOM000148402D
Original Publication Date: 1988-May-31
Included in the Prior Art Database: 2007-Mar-29
Document File: 26 page(s) / 1M

Publishing Venue

Software Patent Institute

Related People

Panangaden, Prakash: AUTHOR [+3]


McCarthy's Amb Cannot Implement Fair MergePrakash Panangaden Vasant Shanbhogue

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 8% of the total text.

Page 1 of 26

McCarthy's Amb Cannot Implement Fair Merge
Prakash Panangaden

Vasant Shanbhogue

 88-91 3 May 1988

Department of Computer Science Comell University

Ithaca, NY 14853-7501

[This page contains 1 picture or other non-text object]

Page 2 of 26

[This page contains 1 picture or other non-text object]

Page 3 of 26

McCarthy 's Amb Cannot Implement Fair Merge

Prakash Panangaden

Vasant Shanbhogue
Computer Science Department, Cornell University

May 3, 1988


  In this paper we establish that fair merge is a powerful non- deterministic primitive that cannot be implemented in terms of other well-known primitives. It is well known that fair merge embodies countable non-determinism. It is also been known that McCarthy's amb embodies countable non-determinism. It had not been known, however, whether amb could implement a fair merge. We show that countable non-determinism together with angelic non-de terminism cannot implement fair merge even in dynamic dataflow networks. This settles a question posed by Abramsky over four years ago. Earlier work had suggested this result by showing that for static dataflow netwprks, one cannot implement fair merge using angelic merge.

1 Introduction

The theory of computability is well established for sequential, determinate programs. When one considers non-determinism in the context of a parallel programming language, the situation is much less clear. We examine the relative expressive power of non-determinate primitives in the context of dynamic dataflow networks. Our main result is that it is impossible to implement a fair merge using so called "angelic non-determinism." The

[This page contains 1 picture or other non-text object]

Page 4 of 26

key point of the result is that one cannot implement fair merge without some sort of time sensitivity built into the primitives.

  The results described in the present paper were suggested by earlier results of Panangaden and Stark -171 that applied to static networks, i.e. to networks whose structure is fixed throughout execution. The techniques used in [li were operational in nature. Similar results were proved in j16: using denotational techniques and continuity arguments. We use a different denotational model suggested by [5].

  A semantic theory appropriate for finite non-determinism was developed by Plotkin [20! using powerdomains. Plotkin's powerdomain techniques cannot handle countable non-determinism. This motivated people to ex- plore techniques that were capable of handling countable non-determinism. Work along these lines was done by Back ',4], Park :19,18], Abramsky [I:, Keller and Panangaden [9,10] and Panangaden :15].

  A powerdomain technique for countable non-determinism has been stud- ied by Apt and Plotkin 133. They develop a powerdomain for countable non-determinism when the underlying domain is flat. Their semantics is for a sequential, i...