Editing Distributed computing (section)

===Properties of distributed systems===
So far the focus has been on ''designing'' a distributed system that solves a given problem. A complementary research problem is ''studying'' the properties of a given distributed system.<ref>{{cite web|url=https://cstheory.stackexchange.com/q/10045|title=Major unsolved problems in distributed systems?|website=cstheory.stackexchange.com|access-date=16 March 2018|archive-date=20 January 2023|archive-url=https://web.archive.org/web/20230120182442/https://cstheory.stackexchange.com/questions/10045/major-unsolved-problems-in-distributed-systems|url-status=live}}</ref><ref>{{cite web|url=http://www.theserverside.com/feature/How-big-data-and-distributed-systems-solve-traditional-scalability-problems|title=How big data and distributed systems solve traditional scalability problems|website=theserverside.com|access-date=16 March 2018|archive-date=17 March 2018|archive-url=https://web.archive.org/web/20180317232027/http://www.theserverside.com/feature/How-big-data-and-distributed-systems-solve-traditional-scalability-problems|url-status=live}}</ref>

The [[halting problem]] is an analogous example from the field of centralised computation: we are given a computer program and the task is to decide whether it halts or runs forever. The halting problem is [[Undecidable problem|undecidable]] in the general case, and naturally understanding the behaviour of a computer network is at least as hard as understanding the behaviour of one computer.<ref name="SvozilIndet11">{{cite book |chapter-url=https://books.google.com/books?id=ep_FCgAAQBAJ&pg=PA112 |chapter=Indeterminism and Randomness Through Physics |title=Randomness Through Computation: Some Answers, More Questions |author=Svozil, K. |editor=Hector, Z. |publisher=World Scientific |pages=112–3 |year=2011 |isbn=9789814462631 |access-date=2018-07-20 |archive-date=2020-08-01 |archive-url=https://web.archive.org/web/20200801024745/https://books.google.com/books?id=ep_FCgAAQBAJ&pg=PA112 |url-status=live }}</ref>

However, there are many interesting special cases that are decidable. In particular, it is possible to reason about the behaviour of a network of finite-state machines. One example is telling whether a given network of interacting (asynchronous and non-deterministic) finite-state machines can reach a deadlock. This problem is [[PSPACE-complete]],<ref>{{harvtxt|Papadimitriou|1994}}, Section 19.3.</ref> i.e., it is decidable, but not likely that there is an efficient (centralised, parallel or distributed) algorithm that solves the problem in the case of large networks.