A distributed system is a network of independent computers that communicate by message passing. This structure for distributed systems leads to three important features: concurrency of processes on the nodes of a distributed system, lack of global time, and independence of component failures from one another. Many examples can be cited for distributed systems, of which the best-known is certainly the Internet. The Internet grew out of the old ARPAnet, a network that was created by the Advanced Research Projects Agency (ARPA--now known as the Defense Advanced Research Projects Agency, DARPA). The military was concerned at the time (late 1960s) with ways to prevent and win nuclear wars, and thus decided to try to create a network that would have the characteristics of being resistant to the failures of individual nodes, and of being uniform in structure (having no specialized nodes). The distributed system called ARPAnet had these features (as most do), and its successor clearly shows these properties even now--many computers connected to the Internet are down at any given instant, usually five to six percent, yet the Internet is always running. Fortunately, however, distributed systems are now designed and used for more useful and practical ends than to wage nuclear wars.
Concurrency is a central notion in all distributed systems—processors run their processes independently, so that multiple processes in the system are capable of execution at a given moment. This is very useful in the sense that concurrent systems are obviously faster than those where execution is sequential, but concurrent systems are much harder to program for, understand or describe mathematically, and prove correct.
There are two major types of distributed systems, synchronous and asynchronous. Synchronous systems are those where a global clock or timer exists, and all processors execute in lock-step, or in rounds, with each processor taking a specific step in a certain round. However, such systems are limited in use and difficult to design. Much more common is the asynchronous distributed system (of which the Internet is an example), where there is no global clock. Events that occur on a single processor of course are ordered by the processor's own clock. If a message is sent from one processor to another over the network, then the send event is considered to be prior to the receive event. By suitably composing these two types of events (i.e., by taking note of the fact that an event prior to a prior event is also a prior event), we obtain the "happens before" relation of Lamport, described by him in a seminal 1978 paper, which is the basis of logical ordering of events according to the partial order described.
Several types of failures are considered in the literature on distributed systems. The most common kind of failure is an omission failure, where a processor or a communication link omits to perform some required action. A processor may crash and thus never respond to a message, or a link may be broken and not allow a message to be delivered. In some literature, the crash failure of a processor is considered to be a kind of failure in its own strength, but it really is a special case of omission failure. An omission failure is the simplest kind of failure that can be encountered in a distributed system. Another kind of failure, one that is far more difficult to design a system to handle, is arbitrary or Byzantine failure (the name "Byzantine" is supposed to describe the complex state of scheming and intrigue said to have obtained in the ancient kingdom of Byzantium, what is now Turkey). A processor that fails by Byzantine failure may deliberately give confusing and inconsistent responses, or may otherwise mislead or hinder other processors. Since a processor that fails by Byzantine failure can always keep quiet among other things, this type of failure is strictly stronger than crash failure.
A basic problem in distributed systems is that of achieving consensus among the processors. Assume that all the processors in a distributed system are given certain input values. The processors may communicate among themselves by message passing, but all of them are required to terminate and come up with the same output value. To make this problem meaningful, we add the condition of validity--that is, if all the processors are given the same arbitrary input, then they decide on that value as output (this is to avoid trivial solutions to consensus arrived at by "fixing" the output in advance regardless of the input).
Consensus (and related problems referenced under the generic rubric of "agreement") are important in showing what it is possible or not possible to achieve in distributed systems under given conditions. For example, a famous 1985 paper by Fischer, Lynch, and Paterson showed that it is impossible to achieve consensus in an asynchronous system even if a single processor fails by crash failure.
The distributed object model is an important extension of object-orientation to the distributed system environment. Instead of having objects located on a single system, we now think of objects being physically distributed on different processors or computers. Distributed object systems may use the client-server architecture with the objects being managed by servers, and the clients making requests of the servers to access the objects' methods. This idea is known as remote method invocation. A similar idea called remote procedure call involves client programs running on one processor calling a procedure running on another processor that runs a server process.
This is the complete article, containing 904 words
(approx. 3 pages at 300 words per page).
