Jfromm: New page: '''Distributed computing''' is the process of aggregating the power of several computing entities to collaboratively run a single computational task in a transparent and coherent way, so t...

2008-09-19T16:46:37Z

New page: '''Distributed computing''' is the process of aggregating the power of several computing entities to collaboratively run a single computational task in a transparent and coherent way, so t...

New page

'''Distributed computing''' is the process of aggregating the power of several computing entities to collaboratively run a single computational task in a transparent and coherent way, so that they appear as a single, centralized system. It is a part of the general theory of systems that are composed of a number of interacting computing elements.
[[Grid_Computing|Grid computing]] is often used synonymously for distributed computing. Grid Computing uses no special [[Distributed Algorithm]]s and is more like parallel computing: it only breaks down complex computing problems into small steps that can be solved in parallel by thousands or even millions of machines at once. The word ''distributed'' here and in
[[Distributed System]]s in general means, as Lamport and Lynch argue (1990), simply
"spread out across space". Thus distributed computing is generally a spatially distributed process
in some form of network.

Distributed computing for general asynchronous systems and
the design of sophisticated [[Distributed Algorithm]]s
is notoriously difficult, because distributed
systems become easily very complex.
Recent approaches like [[Distributed Hash Table]]s (DHT)
emphasize scalability and [[Peer-to-Peer]] aspects.

== Introduction ==

The field of distributed computing started around 1970. At that time, according to Fisher and Merrrit (2003),
scientists and engineers began to imagine a future world of multiple interconnected computers operating
concurrently and collectively. Typical challenges in distributed computing are absence of global time and state,
asynchronous computation, communication delays, failures of communication or processors, and decentralized administration.

The original goal of distributed computing theory research was, as
Fisher and Merrrit argue (2003), to find a general theory of distributed
systems:
"To build a mathematical theory of distributed computing that
would shed light on distributed computing systems just as
Turing machine theory had done for sequential computers.
The hope was to find an abstract distributed model that
would capture the salient features of real distributed systems
while suppressing distracting and unenlightening details of
the physical world. The theory to be constructed was to be
elegant, general, and powerful."

Yet they also say that this original goal was not really reached
"Twenty-plus years later, these goals seem hopelessly
naive. The theory of distributed systems is immensely more
complex than its sequential counterpart. Every one of the distinguishing
elements has seemingly endless plausible variations.
Elegant theoretical assumptions such as pure asynchrony
(no timing assumptions whatsoever) and Byzantine
faults (no assumptions limiting faulty behavior) lead to pessimistic
results that do not jibe well with real-world experience.
Even finding precise specifications for the problems to be
solved by distributed systems has proven to be much more
difficult than expected."

== Centralized vs. Distributed ==

Distributed Computing is the opposite of '''local, centralized computing''', where programs
are confined to a single address space and a single machine or computer. It is
global and decentralized. These two models of computing - local and centralized vs. global
and distributed - are fundamentally different. Distributed Computing involves latency,
partial failure and concurrency. As Waldo et al. noticed in 1994
"Merging the models by attempting to make distributed
computing follow the model of local computing
requires ignoring the different failure modes and basic
indeterminacy inherent in distributed computing, leading
to systems that are unreliable and incapable of scaling
beyond small groups of machines that are geographically
co-located and centrally administered."

== Parallel vs. Distributed ==

The two related fields parallel and distributed computing have many things in common. They
use as Claudia Leopold says (2001):

* Multiple Processors
* Networks which connect the processors
* Multiple computational activities and processes

In both fields the input, output and intermediate data is distributed among many
processors. Parallel and [[Distributed Algorithm]]s tells us
how to solve a given problem using multiple processors, which are connected by
some form of network, communication medium or shared memory.

Yet whereas parallel computing splits a single application up into tasks that
are executed at the same time and is more like a '''top-down''' approach,
distributed computing considers a single application which is executed
as a whole but at different locations and is more like a '''bottom-up''' approach.

Parallel computing is about '''decomposition''': we ask how we can perform a single
application concurrently, how we can divide a computation into
smaller parts which may potentially be executed in parallel.
Distributed computing is about '''composition''': we ask what happens if many
distributed processes interact with each other, and if a global function can
be achieved although there is no global time or state.

In parallel computing, task dependencies are troublesome and disturbing for
computational purposes, which limit the degree of concurrency. If there are
no task dependencies at all, the maximum degree of concurrency is reached and
equals the total number of tasks (Grama et al., 2003).

In distributed computing, dependencies and causal relations are an essential
part of the computation itself. The interaction between the processes is an
essential part of the computation process. The goal is not reach a maximum
degree of concurrency, rather the optimal balance between communication
and computation.

This is the traditional distinction between distributed and parallel
computing. Recently [[Grid_Computing|grid computing]] and projects like SETI@Home
are often used synonymously for distributed computing, although they are
more like parallel computing which is spatially distributed.

In distributed computing we assume a certain microscopic, local behavior
and consider the possible macroscopic, global behavior. In the field of
[[Distributed Algorithm]]s we ask traditionally,
if we can we reach a

# global time (Synchronous Communication or Synchronization, Logical Time)
# global state (Global Snapshots, Deadlock Detection, Termination)
# unified state (Agreement or Consensus, Contention Problems as Election and Mutual Exclusion)

== Articles and Resources ==

[http://www.sunlabs.com/techrep/1994/abstract-29.html A Note on Distributed Computing], Jim Waldo et al., Sun Technical Report (1994) TR-94-29

[http://research.microsoft.com/users/lamport/pubs/lamport-chapter.pdf A Chapter on Distributed Computing], Leslie Lamport and Nancy Lynch, in "Handbook of Theoretical Computer Science", Jan Van Leeuwen (Editor), Chapter 18 (1990) 1157-1199

[http://citeseer.ist.psu.edu/stankovic94distributed.html Distributed Computing], John A. Stankovic (1992)

[http://www.cs.yale.edu/homes/fischer/pubs/appraising.pdf Appraising Two Decades of Distributed Computing Theory Research], Michael J. Fischer and Michael Merrit, Distrib. Computing Vol 16. (2003) 239-247

[http://portal.acm.org/citation.cfm?coll=GUIDE&dl=GUIDE&id=806567 Primitives for distributed computing], Barbara Liskov

== Books ==

Hagit Attiya and Jennifer Welch, ''Distributed Computing: Fundamentals, Simulations, and Advanced Topics'', John Wiley and Sons, Inc. (2004), ISBN 0-471-45324-2

Claudia Leopold, ''Parallel and Distributed Computing: A Survery of Models, Paradigms, and Approaches'', John Wiley and Sons, 2001, ISBN 0-471-35831-2

Ananth Grama, Anshul Gupta, George Karypis, Vipin Kumar, ''Parallel Computing'', Pearson/Addison-Wesley, 2003, ISBN 0-201-64865-2

== Portals and Links ==

[http://directory.google.com/Top/Computers/Computer_Science/Distributed_Computing/ Google Directory] and
[http://dir.yahoo.com/Science/Computer_Science/Distributed_Computing/ Yahoo! Directory] for Distributed Computing.

[http://www.sciencemag.org/content/vol308/issue5723/index.shtml Special Issuse of Science about Distributed Computing], Science Vol. 308 No. 5723 (2005)

[[Category:x-Computing Techniques]]

Distributed Computing - Revision history

Jfromm: New page: '''Distributed computing''' is the process of aggregating the power of several computing entities to collaboratively run a single computational task in a transparent and coherent way, so t...