Editing Deterministic algorithm (section)

== 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 [[Randomness|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 language]]s and especially [[functional programming]] languages make an effort to prevent the above events from happening except under controlled conditions.

The prevalence of [[multi-core processor]]s has resulted in a surge of interest in determinism in parallel programming and challenges of non-determinism have been well documented.<ref>{{cite web | author = Edward A. Lee | url = http://www.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-1.pdf | access-date = 2009-05-29 | title = The Problem with Threads}}</ref><ref>{{cite conference |first1=Robert L. |last1=Bocchino Jr. |first2=Vikram S. |last2=Adve |first3=Sarita V. |last3=Adve |first4=Marc |last4=Snir |title=Parallel Programming Must Be Deterministic by Default |conference=[[USENIX]] Workshop on Hot Topics in Parallelism |year=2009 |url=https://www.usenix.org/legacy/event/hotpar09/tech/full_papers/bocchino/bocchino_html/}}</ref> A number of tools to help deal with the challenges have been proposed<ref>{{cite web | url = http://software.intel.com/en-us/videos/intel-parallel-inspector-thread-checker/ | access-date = 2009-05-29 | title = Intel Parallel Inspector Thread Checker}}</ref><ref>{{cite web | author = Yuan Lin | url = http://developers.sun.com/sunstudio/documentation/product/sd_west_threadAnalyzer.pdf | title = Data Race and Deadlock Detection with Sun Studio Thread Analyzer | access-date = 2009-05-29}}</ref><ref>{{cite web | author = Intel | url = http://software.intel.com/en-us/intel-parallel-inspector | access-date = 2009-05-29 | title = Intel Parallel Inspector}}</ref><ref>{{cite web | url = http://sdtimes.com/link/33497 | title = Intel addresses development life cycle with Parallel Studio | author = David Worthington | access-date = 2009-05-26 | archive-url = https://web.archive.org/web/20090528030044/http://www.sdtimes.com/link/33497 | archive-date = 2009-05-28 | url-status = dead }}</ref> to deal with [[Deadlock (computer science)|deadlock]]s and [[race condition]]s.