Editing Distributed computing (section)

==Theoretical foundations==
{{Main|Distributed algorithm}}
<!-- Many citations are still missing, will add later -->

===Models===
Many tasks that we would like to automate by using a computer are of question–answer type: we would like to ask a question and the computer should produce an answer. In [[theoretical computer science]], such tasks are called [[computational problem]]s. Formally, a computational problem consists of ''instances'' together with a ''solution'' for each instance. Instances are questions that we can ask, and solutions are desired answers to these questions.

Theoretical computer science seeks to understand which computational problems can be solved by using a computer ([[computability theory]]) and how efficiently ([[computational complexity theory]]). Traditionally, it is said that a problem can be solved by using a computer if we can design an [[algorithm]] that produces a correct solution for any given instance. Such an algorithm can be implemented as a [[computer program]] that runs on a general-purpose computer: the program reads a problem instance from [[Information|input]], performs some computation, and produces the solution as [[output (computing)|output]]. Formalisms such as [[random-access machine]]s or [[universal Turing machine]]s can be used as abstract models of a sequential general-purpose computer executing such an algorithm.<ref name="ToomarianNeural92">{{cite book |chapter-url=https://books.google.com/books?id=CKTsCgAAQBAJ&pg=PA214 |chapter=Neural Networks for Real-Time Robotic Applications |title=Parallel Computation Systems For Robotics: Algorithms And Architectures |author=Toomarian, N.B. |author2=Barhen, J. |author3=Gulati, S. |editor=Fijany, A. |editor2=Bejczy, A. |publisher=World Scientific |page=214 |year=1992 |isbn=9789814506175 |access-date=2018-07-20 |archive-date=2020-08-01 |archive-url=https://web.archive.org/web/20200801024715/https://books.google.com/books?id=CKTsCgAAQBAJ&pg=PA214 |url-status=live }}</ref><ref name="SavageModels98">{{cite book |title=Models of Computation: Exploring the Power of Computing |author=Savage, J.E. |publisher=Addison Wesley |page=209 |year=1998 |isbn=9780201895391}}</ref>

The field of concurrent and distributed computing studies similar questions in the case of either multiple computers, or a computer that executes a network of interacting processes: which computational problems can be solved in such a network and how efficiently? However, it is not at all obvious what is meant by "solving a problem" in the case of a concurrent or distributed system: for example, what is the task of the algorithm designer, and what is the concurrent or distributed equivalent of a sequential general-purpose computer?{{citation needed|date=October 2016}}

The discussion below focuses on the case of multiple computers, although many of the issues are the same for concurrent processes running on a single computer.

Three viewpoints are commonly used:
; Parallel algorithms in shared-memory model
* All processors have access to a shared memory. The algorithm designer chooses the program executed by each processor.
* One theoretical model is the [[parallel random-access machine]]s (PRAM) that are used.<ref>{{harvtxt|Cormen|Leiserson|Rivest|1990}}, Section 30.</ref> However, the classical PRAM model assumes synchronous access to the shared memory.
* Shared-memory programs can be extended to distributed systems if the underlying operating system encapsulates the communication between nodes and virtually unifies the memory across all individual systems.
* A model that is closer to the behavior of real-world multiprocessor machines and takes into account the use of machine instructions, such as [[Compare-and-swap]] (CAS), is that of ''asynchronous shared memory''. There is a wide body of work on this model, a summary of which can be found in the literature.<ref>{{harvtxt|Herlihy|Shavit|2008}}, Chapters 2–6.</ref><ref>{{harvtxt|Lynch|1996}}</ref>

; Parallel algorithms in message-passing model
* The algorithm designer chooses the structure of the network, as well as the program executed by each computer.
* Models such as [[Boolean circuits]] and [[sorting network]]s are used.<ref>{{harvtxt|Cormen|Leiserson|Rivest|1990}}, Sections 28 and 29.</ref> A Boolean circuit can be seen as a computer network: each gate is a computer that runs an extremely simple computer program. Similarly, a sorting network can be seen as a computer network: each comparator is a computer.
; Distributed algorithms in message-passing model
* The algorithm designer only chooses the computer program. All computers run the same program. The system must work correctly regardless of the structure of the network.
* A commonly used model is a [[Graph (discrete mathematics)|graph]] with one [[finite-state machine]] per node.

In the case of distributed algorithms, computational problems are typically related to graphs. Often the graph that describes the structure of the computer network ''is'' the problem instance. This is illustrated in the following example.<ref name=":0">TULSIRAMJI GAIKWAD-PATIL College of Engineering & Technology,

Nagpur

Department of Information Technology

Introduction to Distributed Systems[http://www.tgpcet.com/assets/img/IT/Notes/8/Distributed-System.pdf]</ref>

===An example===
Consider the computational problem of finding a coloring of a given graph ''G''. Different fields might take the following approaches:
; Centralized algorithms<ref name=":0" />
* The graph ''G'' is encoded as a string, and the string is given as input to a computer. The computer program finds a coloring of the graph, encodes the coloring as a string, and outputs the result.
; Parallel algorithms
* Again, the graph ''G'' is encoded as a string. However, multiple computers can access the same string in parallel. Each computer might focus on one part of the graph and produce a coloring for that part.
* The main focus is on high-performance computation that exploits the processing power of multiple computers in parallel.
; Distributed algorithms
* The graph ''G'' is the structure of the computer network. There is one computer for each node of ''G'' and one communication link for each edge of ''G''. Initially, each computer only knows about its immediate neighbors in the graph ''G''; the computers must exchange messages with each other to discover more about the structure of ''G''. Each computer must produce its own color as output.
* The main focus is on coordinating the operation of an arbitrary distributed system.<ref name=":0" />

While the field of parallel algorithms has a different focus than the field of distributed algorithms, there is much interaction between the two fields. For example, the [[Cole–Vishkin algorithm]] for graph coloring<ref>{{harvtxt|Cole|Vishkin|1986}}. {{harvtxt|Cormen|Leiserson|Rivest|1990}}, Section 30.5.</ref> was originally presented as a parallel algorithm, but the same technique can also be used directly as a distributed algorithm.

Moreover, a parallel algorithm can be implemented either in a parallel system (using shared memory) or in a distributed system (using message passing).<ref>{{harvtxt|Andrews|2000}}, p. ix.</ref> The traditional boundary between parallel and distributed algorithms (choose a suitable network vs. run in any given network) does not lie in the same place as the boundary between parallel and distributed systems (shared memory vs. message passing).

===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.

===Other problems===
Traditional computational problems take the perspective that the user asks a question, a computer (or a distributed system) processes the question, then produces an answer and stops. However, there are also problems where the system is required not to stop, including the [[dining philosophers problem]] and other similar [[mutual exclusion]] problems. In these problems, the distributed system is supposed to continuously coordinate the use of shared resources so that no conflicts or [[deadlock (computer science)|deadlock]]s occur.

There are also fundamental challenges that are unique to distributed computing, for example those related to ''fault-tolerance''. Examples of related problems include [[Consensus (computer science)|consensus problems]],<ref>{{harvtxt|Lynch|1996}}, Sections 5–7. {{harvtxt|Ghosh|2007}}, Chapter 13.</ref> [[Byzantine fault tolerance]],<ref>{{harvtxt|Lynch|1996}}, p. 99–102. {{harvtxt|Ghosh|2007}}, p. 192–193.</ref> and [[self-stabilisation]].<ref>{{harvtxt|Dolev|2000}}. {{harvtxt|Ghosh|2007}}, Chapter 17.</ref>

Much research is also focused on understanding the ''asynchronous'' nature of distributed systems:
* [[Synchronizer (algorithm)|Synchronizers]] can be used to run synchronous algorithms in asynchronous systems.<ref>{{harvtxt|Lynch|1996}}, Section 16. {{harvtxt|Peleg|2000}}, Section 6.</ref>
* [[Logical clock]]s provide a causal [[happened-before]] ordering of events.<ref>{{harvtxt|Lynch|1996}}, Section 18. {{harvtxt|Ghosh|2007}}, Sections 6.2–6.3.</ref>
* [[Clock synchronization]] algorithms provide globally consistent physical time stamps.<ref>{{harvtxt|Ghosh|2007}}, Section 6.4.</ref>

Note that in distributed systems, [[Latency (engineering)|latency]] should be measured through "99th percentile" because "median" and "average" can be misleading.<ref>{{Cite book |title=Foundations of Data Intensive Applications Large Scale Data Analytics Under the Hood |year=2021 |isbn=9781119713012 |last1=Kamburugamuve |first1=Supun |last2=Ekanayake |first2=Saliya |publisher=John Wiley & Sons }}</ref>

===[[Leader election|Election]]===
''Coordinator election'' (or ''leader election'') is the process of designating a single [[Process (computing)|process]] as the organizer of some task distributed among several computers (nodes). Before the task is begun, all network nodes are either unaware which node will serve as the "coordinator" (or leader) of the task, or unable to communicate with the current coordinator. After a coordinator election algorithm has been run, however, each node throughout the network recognizes a particular, unique node as the task coordinator.<ref name="HaloiApache15">{{cite book |url=https://books.google.com/books?id=Ym9uBgAAQBAJ&pg=PA100 |title=Apache ZooKeeper Essentials |author=Haloi, S. |publisher=Packt Publishing Ltd |pages=100–101 |year=2015 |isbn=9781784398323 |access-date=2018-07-20 |archive-date=2023-01-20 |archive-url=https://web.archive.org/web/20230120182456/https://books.google.com/books?id=Ym9uBgAAQBAJ&pg=PA100 |url-status=live }}</ref>

The network nodes communicate among themselves in order to decide which of them will get into the "coordinator" state. For that, they need some method in order to break the symmetry among them. For example, if each node has unique and comparable identities, then the nodes can compare their identities, and decide that the node with the highest identity is the coordinator.<ref name="HaloiApache15" />

The definition of this problem is often attributed to [[Gérard Le Lann|LeLann]], who formalized it as a method to create a new token in a token [[ring network]] in which the token has been lost.<ref>{{Cite journal|last=LeLann|first=G.|year=1977|title=Distributed systems - toward a formal approach|journal=Information Processing|volume=77|pages=155·160|via=Elsevier}}</ref>

Coordinator election algorithms are designed to be economical in terms of total [[byte]]s transmitted, and time. The algorithm suggested by Gallager, Humblet, and Spira<ref>{{cite journal|date=January 1983|title=A Distributed Algorithm for Minimum-Weight Spanning Trees|url=http://www.apposite-tech.com/blog/wp-content/uploads/2017/09/p66-gallager.pdf |archive-url=https://web.archive.org/web/20170926040957/http://www.apposite-tech.com/blog/wp-content/uploads/2017/09/p66-gallager.pdf |archive-date=2017-09-26 |url-status=live|journal=ACM Transactions on Programming Languages and Systems|volume=5|issue=1|pages=66–77|doi=10.1145/357195.357200|author=[[Robert G. Gallager|R. G. Gallager]], P. A. Humblet, and P. M. Spira|s2cid=2758285}}</ref> for general undirected graphs has had a strong impact on the design of distributed algorithms in general, and won the [[Dijkstra Prize]] for an influential paper in distributed computing.

Many other algorithms were suggested for different kinds of network [[Graph (discrete mathematics)|graph]]s, such as undirected rings, unidirectional rings, complete graphs, grids, directed Euler graphs, and others. A general method that decouples the issue of the graph family from the design of the coordinator election algorithm was suggested by Korach, Kutten, and Moran.<ref>{{cite journal|year=1990|title=A Modular Technique for the Design of Efficient Distributed Leader Finding Algorithms|journal=ACM Transactions on Programming Languages and Systems|volume=12|issue=1|pages=84–101|doi=10.1145/77606.77610|first1=Ephraim|last1=Korach|first2=Shay|last2=Kutten|first3=Shlomo|last3=Moran|author-link2=Shay Kutten|author-link3=Shlomo Moran|url=https://www.cs.technion.ac.il/~moran/r/PS/kkm.pdf |archive-url=https://web.archive.org/web/20070418150944/http://www.cs.technion.ac.il/~moran/r/PS/kkm.pdf |archive-date=2007-04-18 |url-status=live|citeseerx=10.1.1.139.7342|s2cid=9175968}}</ref>

In order to perform coordination, distributed systems employ the concept of coordinators. The coordinator election problem is to choose a process from among a group of processes on different processors in a distributed system to act as the central coordinator. Several central coordinator election algorithms exist.<ref>{{cite web|url=http://www2.cs.uregina.ca/~hamilton/courses/330/notes/distributed/distributed.html|title=Distributed Algorithms|last=Hamilton|first=Howard|access-date=2013-03-03|archive-date=2012-11-24|archive-url=https://web.archive.org/web/20121124002402/http://www2.cs.uregina.ca/~hamilton/courses/330/notes/distributed/distributed.html|url-status=live}}</ref>

===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.