Cornell University
Library
Cornell UniversityLibrary

eCommons

Help
Log In(current)
  1. Home
  2. Cornell Computing and Information Science
  3. Computer Science
  4. Computer Science Technical Reports
  5. McCarthy's Amb Cannot Implement Fair Merge

McCarthy's Amb Cannot Implement Fair Merge

File(s)
88-913.pdf (1.78 MB)
88-913.ps (465.65 KB)
Permanent Link(s)
https://hdl.handle.net/1813/6753
Collections
Computer Science Technical Reports
Author
Panangaden, Prakash
Shanbhogue, Vasant
Abstract

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-determinism 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 networks, one cannot implement fair merge using angelic merge.

Date Issued
1988-05
Publisher
Cornell University
Keywords
computer science
•
technical report
Previously Published as
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR88-913
Type
technical report

Site Statistics | Help

About eCommons | Policies | Terms of use | Contact Us

copyright © 2002-2026 Cornell University Library | Privacy | Web Accessibility Assistance