McCarthy's Amb Cannot Implement Fair Merge

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.