Distributed computing

Distributed computing is a method of computer processing in which different parts of a program run simultaneously on two or more computers that are communicating with each other over a network. Distributed computing is a type of segmented or parallel computing, but the latter term is most commonly used to refer to processing in which different parts of a program run simultaneously on two or more processors that are part of the same computer. While both types of processing require that a program be segmented—divided into sections that can run simultaneously—distributed computing also requires that the division of the program take into account the different environments on which the different sections of the program will be running. For example, two computers are likely to have different file systems and different hardware components.

An example of distributed computing is BOINC, a framework in which large problems can be divided into many small problems which are distributed to many computers. Later, the small results are reassembled into a larger solution.

Distributed computing is a natural result of using networks to enable computers to communicate efficiently. But distributed computing is distinct from computer networking or fragmented computing. The latter refers to two or more computers interacting with each other, but not, typically, sharing the processing of a single program. The World Wide Web is an example of a network, but not an example of distributed computing.

There are numerous technologies and standards used to construct distributed computations, including some which are specially designed and optimized for that purpose, such as Remote Procedure Calls (RPC) or Remote Method Invocation (RMI) or .NET Remoting.

Organization

Organizing the interaction between each computer is of prime importance. In order to be able to use the widest possible range and types of computers, the protocol or communication channel should not contain or use any information that may not be understood by certain machines. Special care must also be taken that messages are indeed delivered correctly and that invalid messages, which would otherwise bring down the system and perhaps the rest of the network, are rejected.

Another important factor is the ability to send software to another computer in a portable way so that it may execute and interact with the existing network. This may not always be possible or practical when using differing hardware and resources, in which case other methods, such as cross-compiling or manually porting this software, must be used.

Goals and advantages

There are many different types of distributed computing systems and many challenges to overcome in successfully designing one. The main goal of a distributed computing system is to connect users and resources in a transparent, open, and scalable way. Ideally this arrangement is drastically more fault tolerant and more powerful than many combinations of stand-alone computer systems.

Openness

Openness is the property of distributed systems such that each subsystem is continually open to interaction with other systems (see references). Web Services protocols are standards which enable distributed systems to be extended and scaled. In general, an open system that scales has an advantage over a perfectly closed and self-contained system.

Consequently, open distributed systems are required to meet the following challenges:

Monotonicity

Once something is published in an open system, it cannot be taken back.

Pluralism

Different subsystems of an open distributed system include heterogeneous, overlapping and possibly conflicting information. There is no central arbiter of truth in open distributed systems.

Unbounded nondeterminism

Asynchronously, different subsystems can come up and go down and communication links can come in and go out between subsystems of an open distributed system. Therefore the time that it will take to complete an operation cannot be bounded in advance (see unbounded nondeterminism).

Drawbacks and disadvantages

See also: Fallacies of Distributed Computing

Technical issues

If not planned properly, a distributed system can decrease the overall reliability of computations if the unavailability of a node can cause disruption of the other nodes. Leslie Lamport famously quipped that: "A distributed system is one in which the failure of a computer you didn't even know existed can render your own computer unusable."^[1]

Troubleshooting and diagnosing problems in a distributed system can also become more difficult, because the analysis may require connecting to remote nodes or inspecting communication between nodes.

Many types of computation are not well suited for distributed environments, typically owing to the amount of network communication or synchronization that would be required between nodes. If bandwidth, latency, or communication requirements are too significant, then the benefits of distributed computing may be negated and the performance may be worse than a non-distributed environment.

Architecture

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 or categories: Client-server, 3-tier architecture, N-tier architecture, Distributed objects, loose coupling, or 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.
• 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.
• 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 servers.
• Tightly coupled (clustered) — refers typically to a set of highly integrated machines that run the same process in parallel, subdividing the task 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 — 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 relationship. Alternatively, a "database-centric" architecture can enable distributed computing to be done without any form of direct inter-process communication, by utilizing a shared database.^[2]

Concurrency

Distributed computing implements a kind of concurrency. It interrelates tightly with concurrent programming so much that they are sometimes not taught as distinct subjects ^[3].

Multiprocessor systems

A multiprocessor system is simply a computer that has more than one CPU on its motherboard. If the operating system is built to take advantage of this, it can run different processes (or different threads belonging to the same process) on different CPUs.

Multicore systems

Intel CPUs from the late Pentium 4 era (Northwood and Prescott cores) employed a technology called Hyperthreading that allowed more than one thread (usually two) to run on the same CPU. The more recent Sun UltraSPARC T1, AMD Athlon 64 X2, AMD Athlon FX, AMD Opteron, Intel Pentium D, Intel Core, Intel Core 2 and Intel Xeon processors feature multiple processor cores to also increase the number of concurrent threads they can run.

Multicomputer systems

A multicomputer may be considered to be either a loosely coupled NUMA computer or a tightly coupled cluster. Multicomputers are commonly used when strong compute power is required in an environment with restricted physical space or electrical power.

Common suppliers include Mercury Computer Systems, CSPI, and SKY Computers.

Common uses include 3D medical imaging devices and mobile radar.

Computing taxonomies

The types of distributed systems are based on Flynn's taxonomy of systems; single instruction, single data (SISD), single instruction, multiple data (SIMD), multiple instruction, single data (MISD), and multiple instruction, multiple data (MIMD). Other taxonomies and architectures available at Computer architecture and in Category:Computer architecture.

Computer clusters

Main article: Cluster computing

A cluster consists of multiple stand-alone machines acting in parallel across a local high speed network. Distributed computing differs from cluster computing in that computers in a distributed computing environment are typically not exclusively running "group" tasks, whereas clustered computers are usually much more tightly coupled. Distributed computing also often consists of machines which are widely separated geographically.

Grid computing

Main article: Grid computing

A grid uses the resources of many separate computers, loosely connected by a network (usually the Internet), to solve large-scale computation problems. Public grids may use idle time on many thousands of computers throughout the world. Such arrangements permit handling of data that would otherwise require the power of expensive supercomputers or would have been impossible to analyze.

Languages

Nearly any programming language that has access to the full hardware of the system could handle distributed programming given enough time and code. Remote procedure calls distribute operating system commands over a network connection. Systems like CORBA, Microsoft DCOM, Java RMI and others, try to map object oriented design to the network. Loosely coupled systems communicate through intermediate documents that are typically human readable (e.g. XML, HTML, SGML, X.500, and EDI).

Languages specifically tailored for distributed programming are:

• Ada programming language ^[4]
  • Alef programming language
  • E programming language
  • Erlang programming language
  • Limbo programming language
  • Oz programming language
  • ZPL (programming language)
  • Orca programming language

  Examples

  Projects

  Main article: List of distributed computing projects

  A variety of distributed computing projects have grown up in recent years. Many are run on a volunteer basis, and involve users donating their unused computational power to work on interesting computational problems. Examples of such projects include the Stanford University Chemistry Department Folding@home project, which is focused on simulations of protein folding to find disease cures and to understand biophysical systems; World Community Grid, an effort to create the world's largest public computing grid to tackle scientific research projects that benefit humanity, run and funded by IBM; SETI@home, which is focused on analyzing radio-telescope data to find evidence of intelligent signals from space, hosted by the Space Sciences Laboratory at the University of California, Berkeley; and distributed.net, which is focused on breaking various cryptographic ciphers.^[5]

  Distributed computing projects also often involve competition with other distributed systems. This competition may be for prestige, or it may be a matter of enticing users to donate processing power to a specific project. For example, stat races are a measure of the work a distributed computing project has been able to compute over the past day or week. This has been found to be so important in practice that virtually all distributed computing projects offer online statistical analyses of their performances, updated at least daily if not in real-time.

  See also

  

  Wikibooks has a book on the topic of

  Distributed Systems
  • Fallacies of Distributed Computing
  • Category:Concurrent programming languages
  • List of distributed computing publications
  • Parallel computing
  • Network Agility
  • Application server
  • Software componentry
  • Distributed computing environment
  • Distributed Resource Management System
  • High-Throughput Computing
  • List of distributed computing projects

  References

  1. ^ Leslie Lamport. Subject: distribution (Email message sent to a DEC SRC bulletin board at 12:23:29 PDT on 28 May 87). Retrieved on 2007-04-28.
  2. ^ A database-centric virtual chemistry system, J Chem Inf Model. 2006 May-Jun;46(3):1034-9
  3. ^ CS236370 Concurrent and Distributed Programming 2002
  4. ^ Ada Reference Manual, ISO/IEC 8652:2005(E) Ed. 3, Annex E Distributed Systems
  5. ^ David P. Anderson (2005-05-23). "A Million Years of Computing". Retrieved on 2006-08-11.

  
  

  Further reading

  • Attiya, Hagit and Welch, Jennifer (2004). Distributed Computing: Fundamentals, Simulations, and Advanced Topics. Wiley-Interscience.  ISBN 0471453242.
  • Lynch, Nancy A (1997). Distributed Algorithms. Morgan Kaufmann.  ISBN 1558603484.
  • Tel, Gerard (1994). Introduction to Distributed Algorithms. Cambridge University Press. 
  • Davies, Antony (June 2004). "Computational Intermediation and the Evolution of Computation as a Commodity". Applied Economics. 
  • Kornfeld, William (January 1981). "The Scientific Community Metaphor". MIT AI (Memo 641). 
  • Hewitt, Carl (August 1983). "Analyzing the Roles of Descriptions and Actions in Open Systems". Proceedings of the National Conference on Artificial Intelligence. 
  • Hewitt, Carl (April 1985). "The Challenge of Open Systems". Byte Magazine. 
  • Hewitt, Carl (1999-10-23–1999-10-27). "Towards Open Information Systems Semantics". Proceedings of 10th International Workshop on Distributed Artificial Intelligence. 
  • Hewitt, Carl (January 1991). "Open Information Systems Semantics". Journal of Artificial Intelligence. 
  • Nadiminti, Dias de Assunção, Buyya (September 2006). "Distributed Systems and Recent Innovations: Challenges and Benefits". InfoNet Magazine, Volume 16, Issue 3, Melbourne, Australia. 

  External links

  • A primer on distributed computing
  • Distributed computing at the Open Directory Project
  • Distributed computing journals at the Open Directory Project
  • Distributed computing conferences at the Open Directory Project
  • MIT's Open Course - Distributed Algorithms
  • Melbourne's Masters Course in Distributed Computing
  • Distributed Computing Frequently Asked Questions (FAQs)
  • DynaOS - Description of a conceptual Distributed Operating Systemca:Computació distribuïda

  cs:Distribuovaný výpočet da:Distribuerede beregninger de:Verteiltes Rechnen el:Κατανεμημένο σύστημα es:Computación distribuida fa:محاسبات توزیع‌شده fr:Calcul distribué ko:분산 컴퓨팅 id:Komputasi terdistribusi it:Calcolo distribuito he:חישוב מבוזר nl:Distributed computing ja:分散コンピューティング nn:Distribuert databehandling pl:Obliczenia rozproszone pt:Computação distribuída ru:Распределённые вычисления sv:Distributed computing vi:Tính toán phân tánlt:Paskirstytas skaičiavimas