Open main menu


A computer program that runs within a distributed system is called a distributed program (and distributed programming is the process of writing such programs).[2] There are many different types of implementations for the message passing mechanism, including pure HTTP, RPC-like connectors and message queues.[3]

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,[4] which communicate with each other via message passing.[5]



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.[6] The terms are nowadays used in a much wider sense, even referring to autonomous processes that run on the same physical computer and interact with each other by message passing.[5]

While there is no single definition of a distributed system,[7] the following defining properties are commonly used as:

  • There are several autonomous computational entities (computers or nodes), each of which has its own local memory.[8]
  • The entities communicate with each other by message passing.[9]

A distributed system may have a common goal, such as solving a large computational problem;[10] the user then perceives the collection of autonomous processors as a unit. Alternatively, each computer may have its own user with individual needs, and the purpose of the distributed system is to coordinate the use of shared resources or provide communication services to the users.[11]

Other typical properties of distributed systems include the following:

  • The system has to tolerate failures in individual computers.[12]

Parallel and distributed computingEdit

(a), (b): a distributed system.
(c): 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.[15] The same system may be characterized both as "parallel" and "distributed"; the processors in a typical distributed system run concurrently in parallel.[16] Parallel computing may be seen as a particular tightly coupled form of distributed computing,[17] and distributed computing may be seen as a loosely coupled form of parallel computing.[7] Nevertheless, it is possible to roughly classify concurrent systems as "parallel" or "distributed" using the following criteria:



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, high-performance parallel computation in a shared-memory multiprocessor uses parallel algorithms while the coordination of a large-scale distributed system uses distributed algorithms.[20]


The use of concurrent processes that communicate by message-passing has its roots in operating system architectures studied in the 1960s.[21] The first widespread distributed systems were local-area networks such as Ethernet, which was invented in the 1970s.[22]

ARPANET, the predecessor of the Internet, was introduced in the late 1960s, and ARPANET e-mail was invented in the early 1970s. E-mail became the most successful application of ARPANET,[23] and it is probably the earliest example of a large-scale distributed application. In addition to ARPANET, and its successor, the Internet, other early worldwide computer networks included Usenet and FidoNet from the 1980s, both of which were used to support distributed discussion systems.[24]

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.[25]



Distributed programming typically falls into one of several basic architectures: client–server, three-tier, n-tier, or peer-to-peer; or categories: loose coupling, or tight coupling.[27]

  • Three-tier: 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 three-tier.
  • n-tier: 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.
  • Peer-to-peer: architectures where there are no special machines that provide a service or manage the network resources.[28]:227 Instead all responsibilities are uniformly divided among all machines, known as peers. Peers can serve both as clients and as servers.[29]



Reasons for using distributed systems and distributed computing may include:



Examples of distributed systems and applications of distributed computing include the following:[32]

Theoretical foundationsEdit




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]


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 machines (PRAM) that are used.[35] 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.
Parallel algorithms in message-passing model
  • Models such as Boolean circuits and sorting networks are used.[38] 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


An exampleEdit


Centralized algorithms[citation needed]
Parallel algorithms
Distributed algorithms
  • The main focus is on coordinating the operation of an arbitrary distributed system.[citation needed]

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 Cole–Vishkin algorithm for graph coloring[39] 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).[40] 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 measuresEdit

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.[41] 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.[42]

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) receive the latest messages from their neighbours, (2) perform arbitrary local computation, and (3) 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.[43]


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.[44] 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).[45] The features of this concept are typically captured with the CONGEST(B) model, which similarly defined as the LOCAL model but where single messages can only contain B bits.

Other problemsEdit


There are also fundamental challenges that are unique to distributed computing. The first example is challenges that are related to fault-tolerance. Examples of related problems include consensus problems,[46] Byzantine fault tolerance,[47] and self-stabilisation.[48]






Coordinator election algorithms are designed to be economical in terms of total bytes transmitted, and time. The algorithm suggested by Gallager, Humblet, and Spira [54] 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.



Properties of distributed systemsEdit

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.[57][58]



See alsoEdit


  1. ^ a b Tanenbaum, Andrew S.; Steen, Maarten van (2002). Distributed systems: principles and paradigms. Upper Saddle River, NJ: Pearson Prentice Hall. ISBN 0-13-088893-1.
  3. ^ Magnoni, L. (2015). "Modern Messaging for Distributed Sytems (sic)". Journal of Physics: Conference Series. 608 (1): 012038. doi:10.1088/1742-6596/608/1/012038. ISSN 1742-6596.
  4. ^ Godfrey (2002).
  6. ^ Lynch (1996), p. 1.
  7. ^ a b Ghosh (2007), p. 10.
  8. ^ Andrews (2000), pp. 8–9, 291. Dolev (2000), p. 5. Ghosh (2007), p. 3. Lynch (1996), p. xix, 1. Peleg (2000), p. xv.
  15. ^ Ghosh (2007), p. 10. Keidar (2008).
  17. ^ Peleg (2000), p. 1.
  18. ^ Papadimitriou (1994), Chapter 15. Keidar (2008).
  19. ^ See references in Introduction.
  20. ^ Bentaleb, A.; Yifan, L.; Xin, J.; et al. (2016). "Parallel and Distributed Algorithms" (PDF). National University of Singapore. Retrieved 20 July 2018.
  21. ^ Andrews (2000), p. 348.
  22. ^ Andrews (2000), p. 32.
  23. ^ Peter (2004), The history of email.
  24. ^ Banks, M. (2012). On the Way to the Web: The Secret History of the Internet and its Founders. Apress. pp. 44–5. ISBN 9781430250746.
  25. ^ Tel, G. (2000). Introduction to Distributed Algorithms. Cambridge University Press. pp. 35–36. ISBN 9780521794831.
  26. ^ Ohlídal, M.; Jaroš, J.; Schwarz, J.; et al. (2006). "Evolutionary Design of OAB and AAB Communication Schedules for Interconnection Networks". In Rothlauf, F.; Branke, J.; Cagnoni, S. (eds.). Applications of Evolutionary Computing. Springer Science & Business Media. pp. 267–78. ISBN 9783540332374.
  27. ^ "Real Time And Distributed Computing Systems" (PDF). ISSN 2278-0661. Retrieved 2017-01-09.
  28. ^ Vigna P, Casey MJ. The Age of Cryptocurrency: How Bitcoin and the Blockchain Are Challenging the Global Economic Order St. Martin's Press January 27, 2015 ISBN 9781250065636
  29. ^ Hieu., Vu, Quang (2010). Peer-to-peer computing : principles and applications. Lupu, Mihai., Ooi, Beng Chin, 1961-. Heidelberg: Springer. p. 16. ISBN 9783642035135. OCLC 663093862.
  30. ^ Lind P, Alm M (2006), "A database-centric virtual chemistry system", J Chem Inf Model, 46 (3): 1034–9, doi:10.1021/ci050360b, PMID 16711722.
  31. ^ Elmasri & Navathe (2000), Section 24.1.2.
  33. ^ Toomarian, N.B.; Barhen, J.; Gulati, S. (1992). "Neural Networks for Real-Time Robotic Applications". In Fijany, A.; Bejczy, A. (eds.). Parallel Computation Systems For Robotics: Algorithms And Architectures. World Scientific. p. 214. ISBN 9789814506175.
  34. ^ Savage, J.E. (1998). Models of Computation: Exploring the Power of Computing. Addison Wesley. p. 209. ISBN 9780201895391.
  35. ^ Cormen, Leiserson & Rivest (1990), Section 30.
  36. ^ Herlihy & Shavit (2008), Chapters 2-6.
  37. ^ Lynch (1996)
  38. ^ Cormen, Leiserson & Rivest (1990), Sections 28 and 29.
  40. ^ Andrews (2000), p. ix.
  42. ^ Papadimitriou (1994), Section 15.2.
  43. ^ Lynch (1996), p. 17–23.
  45. ^ Schneider, J.; Wattenhofer, R. (2011). "Trading Bit, Message, and Time Complexity of Distributed Algorithms". In Peleg, D. (ed.). Distributed Computing. Springer Science & Business Media. pp. 51–65. ISBN 9783642240997.
  48. ^ Dolev (2000). Ghosh (2007), Chapter 17.
  51. ^ Ghosh (2007), Section 6.4.
  52. ^ a b Haloi, S. (2015). Apache ZooKeeper Essentials. Packt Publishing Ltd. pp. 100–101. ISBN 9781784398323.
  53. ^ LeLann, G. (1977). "Distributed systems - toward a formal approach". Information Processing. 77: 155·160 – via Elsevier.
  54. ^ R. G. Gallager, P. A. Humblet, and P. M. Spira (January 1983). "A Distributed Algorithm for Minimum-Weight Spanning Trees" (PDF). ACM Transactions on Programming Languages and Systems. 5 (1): 66–77. doi:10.1145/357195.357200.CS1 maint: Multiple names: authors list (link)
  55. ^ Korach, Ephraim; Kutten, Shay; Moran, Shlomo (1990). "A Modular Technique for the Design of Efficient Distributed Leader Finding Algorithms" (PDF). ACM Transactions on Programming Languages and Systems. 12 (1): 84–101. CiteSeerX doi:10.1145/77606.77610.
  57. ^ "Major unsolved problems in distributed systems?". Retrieved 16 March 2018.
  58. ^ "How big data and distributed systems solve traditional scalability problems". Retrieved 16 March 2018.
  59. ^ Svozil, K. (2011). "Indeterminism and Randomness Through Physics". In Hector, Z. (ed.). Randomness Through Computation: Some Answers, More Questions. World Scientific. pp. 112–3. ISBN 9789814462631.
  60. ^ Papadimitriou (1994), Section 19.3.


Web sites

Further readingEdit

Conference Papers

External linksEdit