| Unbounded Nondeterminism |
Website Links For Unbounded |
Information AboutUnbounded Nondeterminism |
| CATEGORIES ABOUT UNBOUNDED NONDETERMINISM | |
| actor model | |
| concurrency | |
| computational models | |
| process calculi | |
|
ORIGINALLY THOUGHT TO BE IMPOSSIBLE TO IMPLEMENT Edsger Dijkstra argued that it is impossible to implement systems with unbounded nondeterminism. Since it was widely assumed at the time that unbounded nondeterminism was unimplementable, Tony Hoare [1978 suggested that "an efficient implementaton should try to be reasonably fair." This gave rise to the Controversy Over Unbounded Nondeterminism . ARGUMENTS FOR DEALING WITH UNBOUNDED NONDETERMINISM Carl Hewitt {Link without Title} argued otherwise (the Actor Model has the property of unbounded nondeterminism):
NONDETERMINISTIC AUTOMATA Nondeterministic Turing machines have only bounded nondeterminism. Sequential programs containing guarded commands as the only sources of nondeterminism have only bounded nondeterminism [ Edsger Dijkstra 1976]. Briefly, choice nondeterminism is bounded. Gordon Plotkin gave a proof in his original paper on power domains [1976]: :Now the set of initial segments of execution sequences of a given nondeterministic program P, starting from a given state, will form a tree. The branching points will correspond to the choice points in the program. Since there are always only finitely many alternatives at each choice point, the branching factor of the tree is always finite. That is, the tree is finitary. Now König's Lemma says that if every branch of a Finitary tree is finite, then so is the tree itself. In the present case this means that if every execution sequence of P terminates, then there are only finitely many execution sequences. So if an output set of P is infinite, it must contain nonterminating computation . INDETERMINACY VERSUS NONDETERMINISTIC AUTOMATA Will Clinger {Link without Title} provided the following analysis of the above proof by Plotkin: :This proof depends upon the premise that if every node x of a certain infinite branch can be reached by some computation c, then there exists a computation c that goes every node x on the branch. ... Clearly this premise follows not from logic but rather from the interpretation given to choice points. This premise fails for arrival nondeterminism the arrival of messages in the Actor model because of finite delay the arrival of messages . Though each node on an infinite branch must lie on a branch with a limit, the infinite branch need not itself have a limit. Thus the existence of an infinite branch does not necessarily imply a nonterminating computation. UNBOUNDED NONDETERMINISM IN THE ORIGINAL AND LATER VERSION OF CSP Consider a program written in CSP {Link without Title} : | ||
| "guard" class="copylinks" target="_blank"> &rarr  Z!go() Zguard |
||
| "(x:=1)(x:=2)]" class="copylinks" target="_blank">= [abort |
|
|