Distributed Computing
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 is often used synonymously for distributed computing. Grid Computing uses no special Distributed Algorithms 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 Systems 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 Algorithms is notoriously difficult, because distributed systems become easily very complex. Recent approaches like Distributed Hash Tables (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 Algorithms 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 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 Algorithms 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
A Note on Distributed Computing, Jim Waldo et al., Sun Technical Report (1994) TR-94-29
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
Distributed Computing, John A. Stankovic (1992)
Appraising Two Decades of Distributed Computing Theory Research, Michael J. Fischer and Michael Merrit, Distrib. Computing Vol 16. (2003) 239-247
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
Google Directory and Yahoo! Directory for Distributed Computing.
Special Issuse of Science about Distributed Computing, Science Vol. 308 No. 5723 (2005)
