Editing Non-blocking algorithm (section)

{{Short description|Algorithm in a thread whose failure cannot cause another thread to fail}}
{{Distinguish|non-blocking I/O}}

In [[computer science]], an [[algorithm]] is called '''non-blocking''' if failure or [[Scheduling (computing)|suspension]] of any [[thread (computing)|thread]] cannot cause failure or suspension of another thread;<ref>{{cite book|last1=Göetz|first1=Brian|last2=Peierls|first2=Tim|last3=Bloch|first3=Joshua|last4=Bowbeer|first4=Joseph|last5=Holmes|first5=David|last6=Lea|first6=Doug|title=Java concurrency in practice|date=2006|publisher=Addison-Wesley|location=Upper Saddle River, NJ|isbn=9780321349606|page=[https://archive.org/details/javaconcurrencyi00goet/page/41 41]|url-access=registration|url=https://archive.org/details/javaconcurrencyi00goet/page/41}}</ref>  for some operations, these algorithms provide a useful alternative to traditional [[lock (computer science)|blocking implementations]]. A non-blocking algorithm is '''lock-free''' if there is guaranteed system-wide [[Resource starvation|progress]], and '''wait-free''' if there is also guaranteed per-thread progress. "Non-blocking" was used as a synonym for "lock-free" in the literature until the introduction of obstruction-freedom in 2003.<ref name=obs-free>{{cite conference|last1=Herlihy|first1=M.|last2=Luchangco|first2=V.|last3=Moir|first3=M.|title=Obstruction-Free Synchronization: Double-Ended Queues as an Example|conference=23rd [[International Conference on Distributed Computing Systems]]|year=2003|pages=522|url=http://www.cs.brown.edu/people/mph/HerlihyLM03/main.pdf}}</ref>

The word "non-blocking" was traditionally used to describe [[telecommunications network]]s that could route a connection through a set of relays "without having to re-arrange existing calls"{{Quote without source|date=November 2024}} (see [[Clos network]]). Also, if the telephone exchange "is not defective, it can always make the connection"{{Quote without source|date=November 2024}} (see [[nonblocking minimal spanning switch]]).