Topic: non-deterministic processing

Summary

A process is non-deterministic when several equally likely paths can be followed. This is prevalent in goal searching algorithms where either branch may be the correct branch to follow. Non-deterministic algorithms can be multi-processed with a new process for each non-deterministic choice, but the number of generated processes is unbounded. Generally heuristics are used for non-deterministic choices with backtracking on failures. If no choices exist the process may terminate normally, signal an exception, or wait for a possible choice.

Dijkstra has made his guarded selection commands non-deterministic. He finds non-determinism can simplify program proofs since arbitrary selection rules are removed. In a repeated non-deterministic command the processor will make arbitrary choices until no alternatives remain. Temporal relationships in multi-processor or parallel processing systems may be non-deterministic. (cbb 5/80)

Subtopic: process vs. sequential implementation

Quote: a non-deterministic algorithm generates tasks for all branches; easy way to parallel programming [»reynJC5_1970, OK]

Quote: parallel is more natural than sequential; e.g., processing an array seldom requires a definite order [»gellDP7_1974]

Quote: the main advantage of nondeterminism is in specifying a process; allows either implementation

Quote: a process only guarantees execution of some unfinished operation; does not guarantee completion of operations [»brinP11_1978]

Subtopic: OS/robotics and indeterminism

Quote: structure an operating system as layers of insensitive, abstract machines

Related Topics

Topic: asynchronous processing (30 items)
Topic: backtracking (30 items)
Topic: conditional statement language (5 items)
Topic: concurrency (33 items)
Topic: concurrent while in parallel processing (5 items)
Topic: high priority processes (13 items)
Topic: interrupt handler (20 items)
Topic: logic programming (34 items)
Topic: parallel algorithms (15 items)
Topic: parallel control statements (12 items)
Topic: parameter passing by value (5 items)
Topic: task scheduling (49 items)
Topic: what is a computer
(62 items)