Editing Distributed computing (section)

===Complexity measures===
In parallel algorithms, yet another resource in addition to time and space is the number of computers. Indeed, often there is a trade-off between the running time and the number of computers: the problem can be solved faster if there are more computers running in parallel (see [[speedup]]). If a decision problem can be solved in [[polylogarithmic time]] by using a polynomial number of processors, then the problem is said to be in the class [[NC (complexity)|NC]].<ref>{{harvtxt|Arora|Barak|2009}}, Section 6.7. {{harvtxt|Papadimitriou|1994}}, Section 15.3.</ref> The class NC can be defined equally well by using the PRAM formalism or Boolean circuits—PRAM machines can simulate Boolean circuits efficiently and vice versa.<ref>{{harvtxt|Papadimitriou|1994}}, Section 15.2.</ref>

In the analysis of distributed algorithms, more attention is usually paid on communication operations than computational steps. Perhaps the simplest model of distributed computing is a synchronous system where all nodes operate in a lockstep fashion. This model is commonly known as the LOCAL model. During each ''communication round'', all nodes in parallel (1)&nbsp;receive the latest messages from their neighbours, (2)&nbsp;perform arbitrary local computation, and (3)&nbsp;send new messages to their neighbors. In such systems, a central complexity measure is the number of synchronous communication rounds required to complete the task.<ref>{{harvtxt|Lynch|1996}}, p. 17–23.</ref>

This complexity measure is closely related to the [[Diameter (graph theory)|diameter]] of the network. Let ''D'' be the diameter of the network. On the one hand, any computable problem can be solved trivially in a synchronous distributed system in approximately 2''D'' communication rounds: simply gather all information in one location (''D'' rounds), solve the problem, and inform each node about the solution (''D'' rounds).

On the other hand, if the running time of the algorithm is much smaller than ''D'' communication rounds, then the nodes in the network must produce their output without having the possibility to obtain information about distant parts of the network. In other words, the nodes must make globally consistent decisions based on information that is available in their ''local D-neighbourhood''. Many distributed algorithms are known with the running time much smaller than ''D'' rounds, and understanding which problems can be solved by such algorithms is one of the central research questions of the field.<ref>{{harvtxt|Peleg|2000}}, Sections 2.3 and 7. {{harvtxt|Linial|1992}}. {{harvtxt|Naor|Stockmeyer|1995}}.</ref> Typically an algorithm which solves a problem in polylogarithmic time in the network size is considered efficient in this model.

Another commonly used measure is the total number of bits transmitted in the network (cf. [[communication complexity]]).<ref name="SchneiderTrading11">{{cite book |chapter-url=https://books.google.com/books?id=dT6nwpXvES4C&pg=PA51 |chapter=Trading Bit, Message, and Time Complexity of Distributed Algorithms |title=Distributed Computing |author=Schneider, J. |author2=Wattenhofer, R. |editor=Peleg, D. |publisher=Springer Science & Business Media |pages=51–65 |year=2011 |isbn=9783642240997 |access-date=2018-07-20 |archive-date=2020-08-01 |archive-url=https://web.archive.org/web/20200801023020/https://books.google.com/books?id=dT6nwpXvES4C&pg=PA51 |url-status=live }}</ref> The features of this concept are typically captured with the CONGEST(B) model, which is similarly defined as the LOCAL model, but where single messages can only contain B bits.