distributed computing distributed application redirects here for trustless applications see decentralized application distributed information processing redirects here for the computer company see dip research distributed computing is a field of computer science that studies distributed systems a distributed system is a system whose components are located on different networked computers which then communicate and coordinate their actions by passing messages to one another examples of distributed systems vary from soabased systems to massively multiplayer online games to peertopeer applications a computer program that runs within a distributed system is called a distributed program and distributed programming is the process of writing such programs distributed computing also refers to the use of distributed systems to solve computational problems in distributed computing a problem is divided into many tasks each of which is solved by one or more computers introduction the word parallel in terms such as parallel system distributed programming and distributed algorithm originally referred to computer networks where individual computers were physically distributed within some geographical area while there is no single definition of a distributed system the following defining properties are commonly used there are several autonomous computational entities computers or nodes each of which has its own local memory the entities communicate with each other by message passing a distributed system may have a common goal such as solving a large computational problem other typical properties of distributed systems include the following the system has to tolerate failures in individual computers the structure of the system network topology network latency number of computers is not known in advance the system may consist of different kinds of computers and network links and the system may change during the execution of a distributed program each computer has only a limited incomplete view of the system each computer may know only one part of the input parallel and distributed computing a b a distributed systemc a parallel system distributed systems are groups of networked computers which have the same goal for their work the terms concurrent computing parallel computing and distributed computing have a lot of overlap and no clear distinction exists between them nevertheless it is possible to roughly classify concurrent systems as parallel or distributed using the following criteria in parallel computing all processors may have access to a shared memory to exchange information between processors in distributed computing each processor has its own private memory distributed memory information is exchanged by passing messages between the processors the figure on the right illustrates the difference between distributed and parallel systems figure a is a schematic view of a typical distributed system the system is represented as a network topology in which each node is a computer and each line connecting the nodes is a communication link figure b shows the same distributed system in more detail each computer has its own local memory and information can be exchanged only by passing messages from one node to another by using the available communication links figure c shows a parallel system in which each processor has a direct access to a shared memory the situation is further complicated by the traditional uses of the terms parallel and distributed algorithm that do not quite match the above definitions of parallel and distributed systems see below for more detailed discussion nevertheless as a rule of thumb highperformance parallel computation in a sharedmemory multiprocessor uses parallel algorithms while the coordination of a largescale distributed system uses distributed algorithms history the use of concurrent processes that communicate by messagepassing has its roots in operating system architectures studied in the 1960s arpanet the predecessor of the internet was introduced in the late 1960s and arpanet email was invented in the early 1970s email became the most successful application of arpanet the study of distributed computing became its own branch of computer science in the late 1970s and early 1980s the first conference in the field symposium on principles of distributed computing podc dates back to 1982 and its counterpart international symposium on distributed computing disc was first held in ottawa in 1985 as the international workshop on distributed algorithms on graphs architectures various hardware and software architectures are used for distributed computing at a lower level it is necessary to interconnect multiple cpus with some sort of network regardless of whether that network is printed onto a circuit board or made up of loosely coupled devices and cables at a higher level it is necessary to interconnect processes running on those cpus with some sort of communication system distributed programming typically falls into one of several basic architectures clientserver threetier ntier or peertopeer or categories loose coupling or tight coupling clientserver architectures where smart clients contact the server for data then format and display it to the users input at the client is committed back to the server when it represents a permanent change threetier architectures that move the client intelligence to a middle tier so that stateless clients can be used this simplifies application deployment most web applications are threetier ntier architectures that refer typically to web applications which further forward their requests to other enterprise services this type of application is the one most responsible for the success of application servers peertopeer architectures where there are no special machines that provide a service or manage the network resources another basic aspect of distributed computing architecture is the method of communicating and coordinating work among concurrent processes through various message passing protocols processes may communicate directly with one another typically in a masterslave relationship alternatively a databasecentric architecture can enable distributed computing to be done without any form of direct interprocess communication by utilizing a shared database applications reasons for using distributed systems and distributed computing may include the very nature of an application may require the use of a communication network that connects several computers for example data produced in one physical location and required in another location there are many cases in which the use of a single computer would be possible in principle but the use of a distributed system is beneficial for practical reasons for example it may be more costefficient to obtain the desired level of performance by using a cluster of several lowend computers in comparison with a single highend computer a distributed system can provide more reliability than a nondistributed system as there is no single point of failure moreover a distributed system may be easier to expand and manage than a monolithic uniprocessor system examples examples of distributed systems and applications of distributed computing include the following telecommunication networks telephone networks and cellular networks computer networks such as the internet wireless sensor networks routing algorithms network applications world wide web and peertopeer networks massively multiplayer online games and virtual reality communities distributed databases and distributed database management systems network file systems distributed information processing systems such as banking systems and airline reservation systems realtime process control aircraft control systems industrial control systems parallel computation scientific computing including cluster computing and grid computing and various volunteer computing projects see the list of distributed computing projects distributed rendering in computer graphics theoretical foundations distributed algorithm models many tasks that we would like to automate by using a computer are of questionanswer type we would like to ask a question and the computer should produce an answer in theoretical computer science such tasks are called computational problems 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 generalpurpose computer the program reads a problem instance from input performs some computation and produces the solution as output formalisms such as random access machines or universal turing machines can be used as abstract models of a sequential generalpurpose computer executing such an algorithm 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 generalpurpose computer 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 sharedmemory 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 machines pram that are used however the classical pram model assumes synchronous access to the shared memory sharedmemory 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 realworld multiprocessor machines and takes into account the use of machine instructions such as compareandswap 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 parallel algorithms in messagepassing 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 networks are used 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 messagepassing 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 with one finitestate 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 an example consider the computational problem of finding a coloring of a given graph g different fields might take the following approaches centralized algorithms 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 highperformance 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 while the field of parallel algorithms has a different focus than the field of distributed algorithms there is a lot of interaction between the two fields for example the colevishkin algorithm for graph coloring 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 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 tradeoff 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 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 1receive the latest messages from their neighbours 2perform arbitrary local computation and 3send new messages to their neighbors in such systems a central complexity measure is the number of synchronous communication rounds required to complete the task this complexity measure is closely related to the 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 2d 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 dneighbourhood 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 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 the features of this concept are typically captured with the congestb model which similarly defined as the local model but where single messages can only contain b bits other problems traditional computational problems take the perspective that we ask a question a computer or a distributed system processes the question for a while and then produces an answer and stops however there are also problems where we do not want the system to ever stop examples of such problems include 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 deadlocks occur there are also fundamental challenges that are unique to distributed computing the first example is challenges that are related to faulttolerance examples of related problems include consensus problems a lot of research is also focused on understanding the asynchronous nature of distributed systems synchronizers can be used to run synchronous algorithms in asynchronous systems logical clocks provide a causal happenedbefore ordering of events clock synchronization algorithms provide globally consistent physical time stamps election coordinator election or leader election is the process of designating a single 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 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 the definition of this problem is often attributed to lelann who formalized it as a method to create a new token in a token ring network in which the token has been lost coordinator election algorithms are designed to be economical in terms of total bytes transmitted and time the algorithm suggested by gallager humblet and spira 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 kind of network graphs 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 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 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 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 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 however there are many interesting special cases that are decidable in particular it is possible to reason about the behaviour of a network of finitestate machines one example is telling whether a given network of interacting asynchronous and nondeterministic finitestate machines can reach a deadlock this problem is pspacecomplete ie it is decidable but it is not likely that there is an efficient centralised parallel or distributed algorithm that solves the problem in the case of large networks appscale boinc code mobility decentralized computing distributed algorithm distributed algorithmic mechanism design distributed cache distributed operating system edsger w dijkstra prize in distributed computing fog computing foldinghome grid computing inferno jungle computing layered queueing network library oriented architecture loa list of distributed computing conferences list of distributed computing projects list of important publications in concurrent parallel and distributed computing model checking parallel distributed processing parallel programming model plan 9 from bell labs shared nothing architecture notes books andrews gregory r 2000 foundations of multithreaded parallel and distributed programming addisonwesley isbn0201357526 arora sanjeev barak boaz 2009 computational complexity a modern approach cambridge isbn9780521424264 cormen thomas h leiserson charles e rivest ronald l 1990 introduction to algorithms 1st ed mit press isbn0262031418 dolev shlomi 2000 selfstabilization mit press isbn0262041782 elmasri ramez navathe shamkant b 2000 fundamentals of database systems 3rd ed addisonwesley isbn0201542633 ghosh sukumar 2007 distributed systems an algorithmic approach chapman hallcrc isbn9781584885641 lynch nancy a 1996 distributed algorithms morgan kaufmann isbn1558603484 herlihy maurice p shavit nir n 2008 the art of multiprocessor programming morgan kaufmann isbn0123705916 papadimitriou christos h 1994 computational complexity addisonwesley isbn0201530821 peleg david 2000 distributed computing a localitysensitive approach siam isbn0898714648 articles cole richard vishkin uzi 1986 deterministic coin tossing with applications to optimal parallel list ranking information and control 70 1 3253 doi101016s0019995886800237 keidar idit 2008 distributed computing column 32 the year in review acm sigact news 39 4 5354 doi10114514663901466402 linial nathan 1992 locality in distributed graph algorithms siam journal on computing 21 1 193201 citeseerx10114716378 doi1011370221015 naor moni stockmeyer larry 1995 what can be computed locally pdf siam journal on computing 24 6 12591277 doi101137s0097539793254571 web sites godfrey bill 2002 a primer on distributed computing peter ian 2004 ian peters history of the internet retrieved 20090804 books attiya hagit and jennifer welch 2004 distributed computing fundamentals simulations and advanced topics wileyinterscience isbn0471453242 christian cachin rachid guerraoui lus rodrigues 2011 introduction to reliable and secure distributed programming 2 ed springer isbn9783642152597 coulouris george et al 2011 distributed systems concepts and design 5th edition addisonwesley isbn0132143011 faber jim 1998 java distributed computing oreilly java distributed computing by jim faber 1998 garg vijay k 2002 elements of distributed computing wileyieee press isbn0471036005 tel gerard 1994 introduction to distributed algorithms cambridge university press chandy mani et al parallel program design articles keidar idit rajsbaum sergio eds 20002009 distributed computing column acm sigact news birrell a d levin r schroeder m d needham r m april 1982 grapevine an exercise in distributed computing pdf communications of the acm 25 4 260274 doi101145358468358487 conference papers c rodrguez m villagra and b barn asynchronous team algorithms for boolean satisfiability bionetics2007 pp6669 2007 wikimedia commons has media related to distributed computing distributed computing at curlie distributed computing journals at curlie vteparallel computinggeneral distributed computing parallel computing massively parallel cloud computing highperformance computing multiprocessing manycore processor gpgpu computer network systolic array levels bit instruction thread task data memory loop pipeline multithreading temporal simultaneous smt speculative spmt preemptive cooperative clustered multithread cmt hardware scout theory pram model analysis of parallel algorithms amdahls law gustafsons law cost efficiency karpflatt metric slowdown speedup elements process thread fiber instruction window array data structure coordination multiprocessing memory coherency cache coherency cache invalidation barrier synchronization application checkpointing programming stream processing dataflow programming models implicit parallelism explicit parallelism concurrency nonblocking algorithm hardware flynns taxonomy sisd simd simt misd mimd dataflow architecture pipelined processor superscalar processor vector processor multiprocessor symmetric asymmetric memory shared distributed distributed shared uma numa coma massively parallel computer computer cluster grid computer hardware acceleration apis ateji px boostthread chapel charm cilk coarray fortran cuda dryad c amp global arrays mpi openmp opencl openhmpp openacc tpl plinq pvm posix threads raftlib upc tbb zpl problems deadlock livelock deterministic algorithm embarrassingly parallel parallel slowdown race condition software lockout scalability starvation category parallel computing media related to parallel computing at wikimedia commons vteedsger dijkstranotable works a primer of algol 60 programming book structured programming book a discipline of programming book a method of programming book predicate calculus and program semantics book selected writings on computing a personal perspective book selected papers ewd manuscripts a note on two problems in connexion with graphs cooperating sequential processes solution of a problem in concurrent programming control the structure of the themultiprogramming system go to statement considered harmful notes on structured programming the humble programmer programming considered as a human activity how do we tell truths that might hurt on the role of scientific thought selfstabilizing systems in spite of distributed control on the cruelty of really teaching computer science main research areas theoretical computing science software engineering systems science algorithm design concurrent computing distributed computing formal methods programming methodology programming language research program design and development software architecture philosophy of computer programming and computing science scientific contributionsconcepts and methods algol 60 implementation call stack concurrency concurrent programming cooperating sequential processes critical section deadly embrace deadlock dining philosophers problem dutch national flag problem faulttolerant system gotoless programming guarded command language layered structure in software architecture levels of abstraction multithreaded programming mutual exclusion mutex producerconsumer problem bounded buffer problem program families predicate transformer semantics process synchronization selfstabilizing distributed system semaphore programming separation of concerns sleeping barber problem software crisis structured analysis structured programming the multiprogramming system unbounded nondeterminism weakest precondition calculus algorithms bankers algorithm dijkstras algorithm djp algorithm prims algorithm dijkstrascholten algorithm dekkers algorithm generalization smoothsort shuntingyard algorithm tricolor marking algorithm concurrent algorithms distributed algorithms deadlock prevention algorithms mutual exclusion algorithms selfstabilizing algorithms related people shlomi dolev per brinch hansen tony hoare olejohan dahl leslie lamport david parnas adriaan van wijngaarden niklaus wirth other topics dijkstra prize edsger w dijkstra prize in distributed computing centrum wiskunde informatica ew dijkstra archive university of texas at austin list of pioneers in computer science list of important publications in computer science list of important publications in theoretical computer science list of important publications in concurrent parallel and distributed computing international symposium on stabilization safety and security of distributed systems wikiquote 