The dream behind interconnecting large numbers of computers has been to have their combined capabilities serve users as one. This distributed computer would compose its resources so as to offer functionality, dependability, and performance, that far exceed those offered by a single isolated computer. This dream has started to be realized, insofar as functionality is concerned, with such widely accepted protocols as the Domain Name Server (DNS) and the World-wide Web (WWW). These protocols compose large numbers of interconnected computers into a single system far superior in functionality than a single centralized system, yet whose distribution is transparent to the user.
There are no similar examples yet of protocols that are deployed on a large scale, that exploit the inherent failure independence and redundancy of distributed systems, to achieve dependability that is higher than that offered by isolated computers. For a service to be highly dependable, it must be both highly available, in the sense of the probability that a request for the service will be accepted, and highly reliable, as measured by the conditional probability that the service will be carried through to successful completion, given that the original invocation was admitted. Dependability becomes more critical as protocols require the cooperation of more sites, to achieve distributed functionality or distributed performance. As the number of sites involved in a computation increases, the likelihood decreases that the distributed system will deliver its functionality with acceptable availability and reliability.