wikademia>Wikademia: http://en.wikipedia.org/wiki/Distributed_computing

2009-10-31T18:08:10Z

http://en.wikipedia.org/wiki/Distributed_computing

New page

'''Distributed computing''' is a field of [[computer science]] that studies distributed systems. A '''distributed system''' consists of multiple autonomous [[computer]]s that communicate through a [[computer network]]. The computers interact with each other in order to achieve a common goal. A [[computer program]] that runs in a distributed system is called a '''distributed program''', and '''distributed programming''' is the process of writing such programs.<ref>{{harvtxt|Andrews|2000}}. {{harvtxt|Dolev|2000}}. {{harvtxt|Ghosh|2007}}, p. 10.</ref>

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 computer.<ref>{{harvtxt|Godfrey|2002}}.</ref>

==Introduction==

The word ''distributed'' in terms such as "distributed computing", "distributed system", "distributed programming", and "[[distributed algorithm]]" originally referred to computer networks where individual computers were physically distributed within some geographical area.<ref>{{harvtxt|Lynch|1996}}, p. 1.</ref> The terms are nowadays used in a much wider sense, even when referring to autonomous [[Process (computing)|processes]] that run on the same physical computer and interact with each other by message passing.<ref>{{harvtxt|Andrews|2000}}, p. 291–292. {{harvtxt|Dolev|2000}}, p. 5.</ref>

While there is no single definition of a distributed system,<ref>{{harvtxt|Ghosh|2007}}, p. 10.</ref> the following defining properties are commonly used:
* There are several autonomous computational entities, each of which has its own local [[Memory (computers)|memory]].<ref>{{harvtxt|Andrews|2000}}, p. 8–9, 291. {{harvtxt|Dolev|2000}}, p. 5. {{harvtxt|Ghosh|2007}}, p. 3. {{harvtxt|Lynch|1996}}, p. xix, 1. {{harvtxt|Peleg|2000}}, p. xv.</ref>
* The entities communicate with each other by [[message passing]].<ref>{{harvtxt|Andrews|2000}}, p. 291. {{harvtxt|Ghosh|2007}}, p. 3. {{harvtxt|Peleg|2000}}, p. 4.</ref>
In this article, the computational entities are called ''computers'' or ''[[Node (networking)|nodes]]''.

A distributed system may have a common goal, such as solving a large computational problem.<ref>{{harvtxt|Ghosh|2007}}, p. 3–4. {{harvtxt|Peleg|2000}}, p. 1.</ref> 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.<ref>{{harvtxt|Ghosh|2007}}, p. 4. {{harvtxt|Peleg|2000}}, p. 2.</ref>

Other typical properties of distributed systems include the following:
* The system has to [[Fault-tolerance|tolerate failures]] in individual computers.<ref>{{harvtxt|Ghosh|2007}}, p. 4, 8. {{harvtxt|Lynch|1996}}, p. 2–3. {{harvtxt|Peleg|2000}}, p. 4.</ref>
* 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.<ref>{{harvtxt|Lynch|1996}}, p. 2. {{harvtxt|Peleg|2000}}, p. 1.</ref>
* Each computer has only a limited, incomplete view of the system. Each computer may know only one part of the input.<ref>{{harvtxt|Ghosh|2007}}, p. 7. {{harvtxt|Lynch|1996}}, p. xix, 2. {{harvtxt|Peleg|2000}}, p. 4.</ref>

[[File:Distributed-parallel.svg|thumb|right|260px|(a)–(b) A distributed system.<br/> (c) A parallel system.]]

===Parallel or distributed computing?===

The terms "[[concurrent computing]]", "[[parallel computing]]", and "distributed computing" have a lot of overlap, and no clear distinction exists between them.<ref>{{harvtxt|Ghosh|2007}}, p. 10. {{harvtxt|Keidar|2008}}.</ref> The same system may be characterised both as "parallel" and "distributed"; the processors in a typical distributed system run concurrently in parallel.<ref>{{harvtxt|Lynch|1996}}, p. xix, 1–2. {{harvtxt|Peleg|2000}}, p. 1.</ref> Parallel computing may be seen as a particular tightly-coupled form of distributed computing,<ref>{{harvtxt|Peleg|2000}}, p. 1.</ref> and distributed computing may be seen as a loosely-coupled form of parallel computing.<ref>{{harvtxt|Ghosh|2007}}, p. 10.</ref> Nevertheless, it is possible to roughly classify concurrent systems as "parallel" or "distributed" using the following criteria:
* In parallel computing, all processors have access to a [[shared memory]]. Shared memory can be used to exchange information between processors.<ref>{{harvtxt|Papadimitriou|1994}}, Chapter 15. {{harvtxt|Keidar|2008}}.</ref>
* In distributed computing, each processor has its own private memory ([[distributed memory]]). Information is exchanged by passing messages between the processors.<ref>See references in [[#Introduction|Introduction]].</ref>
The figure on the right illustrates the difference between distributed and parallel systems. Figure (a) is a schematic view of a typical distributed system; as usual, the system is represented as a [[Graph (mathematics)|graph]] in which each node (vertex) is a computer and each edge (line between two 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 the section [[#Theoretical foundations|Theoretical foundations]] 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.

==History==

The use of concurrent processes that communicate by message-passing has its roots in [[operating system]] architectures studied in 1960s.<ref>{{harvtxt|Andrews|2000}}, p. 348.</ref> The first wide-spread distributed systems were [[local-area networks]] such as [[Ethernet]] that was invented in 1970s.<ref>{{harvtxt|Andrews|2000}}, p. 32.</ref>

[[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,<ref>{{harvtxt|Peter|2004}}, [http://www.nethistory.info/History%20of%20the%20Internet/email.html The history of email].</ref> and it is probably the earliest example of a large-scale distributed application. In addition to ARPANET and its successor Internet, other early worldwide computer networks included [[Usenet]] and [[FidoNet]] from 1980s, both of which were used to support distributed discussion systems.

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 European counterpart [[International Symposium on Distributed Computing]] (DISC) was first held in 1985.

==Applications==

There are two main reasons for using distributed systems and distributed computing. First, the very nature of the application may ''require'' the use of a communication network that connects several computers. For example, data is produced in one physical location and it is needed in another location.

Second, 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 cost-efficient to obtain the desired level of performance by using a [[Cluster (computing)|cluster]] of several low-end computers, in comparison with a single high-end computer. A distributed system can be more reliable than a non-distributed 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.<ref>{{harvtxt|Elmasri|Navathe|2000}}, Section 24.1.2.</ref>

Examples of distributed systems and applications of distributed computing include the following:<ref>{{harvtxt|Andrews|2000}}, p. 10–11. {{harvtxt|Ghosh|2007}}, p. 4–6. {{harvtxt|Lynch|1996}}, p. xix, 1. {{harvtxt|Peleg|2000}}, p. xv. {{harvtxt|Elmasri|Navathe|2000}}, Section 24.</ref>
*[[Telecommunication]] networks:
**[[Telephone network]]s and [[cellular network]]s.
**[[Computer network]]s such as the [[Internet]].
**[[Wireless sensor networks]].
**[[Routing algorithm]]s.
*Network applications:
**[[World wide web]] and [[peer-to-peer network]]s.
**[[Massively multiplayer online game]]s and [[virtual reality]] communities.
**[[Distributed database]]s and [[distributed database management system]]s.
**[[Network file system]]s.
**Distributed information processing systems such as banking systems and airline reservation systems.
*Real-time 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==
{{main|Distributed algorithm}}


===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 (computer science)|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 [[input]], performs some computation, and produces the solution as [[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.

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 and/or distributed equivalent of a sequential general-purpose computer?

The discussion below focusses 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 computers have access to a shared memory. The algorithm designer chooses the program executed by each computer.
*One theoretical model is the [[parallel random access machine]]s (PRAM) are used.<ref>{{harvtxt|Cormen|Leiserson|Rivest|1990}}, Section 30.</ref> However, the classical PRAM model assumes synchronous access to the shared memory.
*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 (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.

===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 colouring 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 neighbours 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 colour 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 [[Cole–Vishkin algorithm]] for graph colouring<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===

A centralised algorithm is efficient if it does not require much time (number of computational steps) or space (amount of memory). These complexity measures give rise to complexity classes such as [[P (complexity)|P]] ([[decision problem]]s solvable in polynomial time) and [[PSPACE]] (decision problems solvable in polynomial space).

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. 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 neighbours. 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 produces 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 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>

Other commonly used measures are the total number of bits transmitted in the network (cf. [[communication complexity]]).

===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 [[deadlock]]s occur.

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

A lot of 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>

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

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 it is not likely that there is an efficient (centralised, parallel or distributed) algorithm that solves the problem in the case of large networks.

==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 [[Process (computing)|processes]] running on those CPUs with some sort of [[communication system]].

Distributed programming typically falls into one of several basic architectures or categories: [[Client-server]], [[Three-tier (computing)|3-tier architecture]], [[Multitier architecture|N-tier architecture]], [[Distributed object]]s, [[loose coupling]], or [[Computer cluster|tight coupling]].

* [[Client-server]] — Smart client code contacts the server for data, then formats and displays it to the user. Input at the client is committed back to the server when it represents a permanent change.
* [[Three-tier (computing)|3-tier architecture]] — Three tier systems move the client intelligence to a middle tier so that stateless clients can be used. This simplifies application deployment. Most web applications are 3-Tier.
* [[Multitier architecture|N-tier architecture]] — N-Tier refers 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 server]]s.
* [[Computer cluster|Tightly coupled]] (clustered) — refers typically to a cluster of machines that closely work together, running a shared process in parallel. The task is subdivided in parts that are made individually by each one and then put back together to make the final result.
* [[Peer-to-peer]] — an architecture where there is no special machine or machines that provide a service or manage the network resources. Instead all responsibilities are uniformly divided among all machines, known as peers. Peers can serve both as clients and servers.
* [[Space based architecture|Space based]] — refers to an infrastructure that creates the illusion (virtualization) of one single address-space. Data are transparently replicated according to application needs. Decoupling in time, space and reference is achieved.

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 [[Master-slave (technology)|master/slave]] relationship. Alternatively, a [[Database-centric architecture|"database-centric" architecture]] can enable distributed computing to be done without any form of direct [[inter-process communication]], by utilizing a shared [[database]].<ref>[http://www.ncbi.nlm.nih.gov/sites/entrez?db=pubmed&list_uids=16711722&cmd=Retrieve A database-centric virtual chemistry system, J Chem Inf Model. 2006 May-Jun;46(3):1034-9]</ref>

==See also==

* [[List of important publications in concurrent, parallel, and distributed computing]]
* [[Edsger W. Dijkstra Prize in Distributed Computing]]
* [[List of distributed computing conferences]]
* [[List of distributed computing projects]]

==Notes==
{{reflist|2}}

==References==

;Books
*{{citation
| last=Andrews | first=Gregory R.
| title=Foundations of Multithreaded, Parallel, and Distributed Programming
| publisher=[[Addison–Wesley]]
| year=2000
| isbn=0-201-35752-6
}}. 
*{{citation
| last1=Arora | first1=Sanjeev | authorlink1=Sanjeev Arora
| last2=Barak | first2=Boaz
| title=Computational Complexity – A Modern Approach
| publisher=[[Cambridge University Press|Cambridge]]
| year=2009
| isbn=978-0-521-42426-4
}}. 
*{{citation
| last1=Cormen | first1=Thomas H. | authorlink1=Thomas H. Cormen
| last2=Leiserson | first2=Charles E. | authorlink2=Charles E. Leiserson
| last3=Rivest | first3=Ronald L. | authorlink3=Ron Rivest
| title=[[Introduction to Algorithms]]
| publisher=[[MIT Press]]
| year=1990
| edition=1st
| isbn=0-262-03141-8
}}. 
*{{citation
| last=Dolev | first=Shlomi | authorlink=Shlomi Dolev
| title=Self-Stabilization
| publisher=[[MIT Press]]
| year=2000
| isbn=0-262-04178-2
}}. 
*{{citation
| last1=Elmasri | first1=Ramez
| last2=Navathe | first2=Shamkant B. | authorlink2=Shamkant Navathe
| title=Fundamentals of Database Systems
| publisher=[[Addison–Wesley]]
| edition=3rd
| year=2000
| isbn=0-201-54263-3
}}. 
*{{citation
| last=Ghosh | first=Sukumar
| title=Distributed Systems – An Algorithmic Approach
| publisher=Chapman & Hall/CRC
| year=2007
| isbn=978-1-58488-564-1
}}. 
*{{citation
| last=Lynch | first=Nancy A. | authorlink=Nancy Lynch
| title=Distributed Algorithms
| publisher=[[Morgan Kaufmann Publishers|Morgan Kaufmann]]
| year=1996
| isbn=1-55860-348-4
}}. 
*{{citation
| last1=Herlihy| first1=Maurice P. | authorlink1=Maurice Herlihy
| last2=Shavit | first2=Nir N. | authorlink2=Nir Shavit
| title=The Art of Multiprocessor Programming
| publisher=[[Morgan Kaufmann Publishers|Morgan Kaufmann]]
| year=2008
| isbn=0-12-370591-6
}}. 
*{{citation
| last=Papadimitriou | first=Christos H. | authorlink=Christos Papadimitriou
| title=Computational Complexity
| publisher=[[Addison–Wesley]]
| year=1994
| isbn=0-201-53082-1
}}. 
*{{citation
| last=Peleg | first=David | authorlink=David Peleg (scientist)
| title=Distributed Computing: A Locality-Sensitive Approach
| publisher=[[Society for Industrial and Applied Mathematics|SIAM]]
| year=2000
| isbn=0-89871-464-8
| url=http://www.ec-securehost.com/SIAM/DT05.html
}}. 
;Articles
* {{Citation
| last1 = Cole | first1 = Richard
| last2 = Vishkin | first2 = Uzi | authorlink2=Uzi Vishkin
| year = 1986
| title = Deterministic coin tossing with applications to optimal parallel list ranking
| journal = Information and Control
| volume = 70
| issue = 1
| pages = 32–53
| doi = 10.1016/S0019-9958(86)80023-7
}}.
*{{citation
| last1=Keidar | first1=Idit
| title=Distributed computing column 32 – The year in review
| journal=[[ACM SIGACT News]]
| volume=39
| issue=4
| year=2008
| pages=53–54
| url=http://webee.technion.ac.il/~idish/sigactNews/#column%2032
}}. 
*{{citation
| last=Linial | first=Nathan
| doi=10.1137/0221015
| title=Locality in distributed graph algorithms
| journal=SIAM Journal on Computing
| volume=21
| number=1
| year=1992
| pages=193–201
}}.
*{{citation
| last1=Naor | first1=Moni | authorlink1=Moni Naor
| last2=Stockmeyer | first2=Larry | authorlink2=Larry Stockmeyer
| doi=10.1137/S0097539793254571
| title=What can be computed locally?
| journal=SIAM Journal on Computing
| volume=24
| number=6
| year=1995
| pages=1259–1277
}}.
;Web sites
*{{cite web
| last=Godfrey | first=Bill
| url=http://www.bacchae.co.uk/docs/dist.html
| title=A primer on distributed computing
| year=2002
}}
*{{cite web
| last=Peter | first=Ian
| url=http://www.nethistory.info/History%20of%20the%20Internet/
| title=Ian Peter's History of the Internet
| year=2004
| accessdate=2009-08-04
}}

==Further reading==

;Books
*{{cite book|first=Gerard|last=Tel |title=Introduction to Distributed Algorithms| publisher=Cambridge University Press| year=1994}}
*{{cite book|author=Attiya, Hagit and Welch, Jennifer|title=Distributed Computing: Fundamentals, Simulations, and Advanced Topics| publisher=Wiley-Interscience| year=2004}} ISBN 0471453242.

;Articles
*{{citation
| editor1-last=Keidar | editor1-first=Idit
| editor2-last=Rajsbaum | editor2-first=Sergio
| url=http://webee.technion.ac.il/~idish/sigactNews/
| contribution=Distributed computing column
| title=[[ACM SIGACT News]]
| year=2000–2009
}}.

==External links==

*{{dmoz|Computers/Computer_Science/Distributed_Computing/|Distributed computing}}
*{{dmoz|Computers/Computer_Science/Distributed_Computing/Publications/|Distributed computing journals}}

{{Parallel_computing}}

{{DEFAULTSORT:Distributed Computing}}
[[Category:Distributed computing| ]]

About distributed computing - Revision history

wikademia>Wikademia: http://en.wikipedia.org/wiki/Distributed_computing