Deterministic algorithm
In computer science, a deterministic algorithm is an algorithm that, given a particular input, will always produce the same output, with the underlying machine always passing through the same sequence of states. Deterministic algorithms are by far the most studied and familiar kind of algorithm, as well as one of the most practical, since they can be run on real machines efficiently.
Formally, a deterministic algorithm computes a
Formal definition
Deterministic algorithms can be defined in terms of a
Examples of particular
Non-deterministic algorithms
A variety of factors can cause an algorithm to behave in a way which is not deterministic, or non-deterministic:
- If it uses an external state other than the input, such as user input, a global variable, a hardware timer value, a random value, or stored disk data.
- If it operates in a way that is timing-sensitive, for example, if it has multiple processors writing to the same data at the same time. In this case, the precise order in which each processor writes its data will affect the result.
- If a hardware error causes its state to change in an unexpected way.
Although real programs are rarely purely deterministic, it is easier for humans as well as other programs to reason about programs that are. For this reason, most programming languages and especially functional programming languages make an effort to prevent the above events from happening except under controlled conditions.
The prevalence of multi-core processors has resulted in a surge of interest in determinism in parallel programming and challenges of non-determinism have been well documented.[1][2] A number of tools to help deal with the challenges have been proposed[3][4][5][6] to deal with deadlocks and race conditions.
Disadvantages of determinism
It is advantageous, in some cases, for a program to exhibit nondeterministic behavior. The behavior of a card shuffling program used in a game of
Note that a negative answer to the
Determinism categories in languages
Mercury
The mercury logic-functional programming language establishes different determinism categories for predicate modes as explained in the reference.[8][9]
Haskell
Haskell provides several mechanisms:
- Non-determinism or notion of Fail
- Neterminism/non-det with multiple solutions
ML family and derived languages
As seen in Standard ML, OCaml and Scala
- The option type includes the notion of success.
Java
In Java, the null reference value may represent an unsuccessful (out-of-domain) result.
See also
References
- ^ Edward A. Lee. "The Problem with Threads" (PDF). Retrieved 2009-05-29.
- ^ Bocchino Jr., Robert L.; Adve, Vikram S.; Adve, Sarita V.; Snir, Marc (2009). Parallel Programming Must Be Deterministic by Default. USENIX Workshop on Hot Topics in Parallelism.
- ^ "Intel Parallel Inspector Thread Checker". Retrieved 2009-05-29.
- ^ Yuan Lin. "Data Race and Deadlock Detection with Sun Studio Thread Analyzer" (PDF). Retrieved 2009-05-29.
- ^ Intel. "Intel Parallel Inspector". Retrieved 2009-05-29.
- ^ David Worthington. "Intel addresses development life cycle with Parallel Studio". Archived from the original on 2009-05-28. Retrieved 2009-05-26.
- ^ McGraw, Gary; Viega, John. "Make your software behave: Playing the numbers: How to cheat in online gambling". IBM. Archived from the original on 2008-03-13. Retrieved 2007-07-02.
- ^ "Determinism categories in the Mercury programming language". Archived from the original on 2012-07-03. Retrieved 2013-02-23.
- ^ "Mercury predicate modes". Archived from the original on 2012-07-03. Retrieved 2013-02-25.
- ^ "Representing failure using the Maybe monad".
- ^ "The class MonadPlus".