Editing Distributed computing (section)

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