1 - Introduction

Summary

In the past two decades, distributed computing has evolved rapidly from a virtually non-existent to an important area in computer science research. As hardware costs declined, single mainframe computers with a few simple terminals were replaced by all kinds of general and special purpose computers and workstations, as the latter became more cost effective. At many sites it became necessary to interconnect all these computers to make communication and file exchanges possible, thus creating a computer network. Given a set of computers that can communicate, it is also desirable that they can cooperate in some sense, for example, to contribute to one and the same computation. Thus a network of computers is turned into a distributed system, capable of performing distributed computations. The field of distributed computing is concerned with the problems that arise in the cooperation and coordination between computers in performing distributed tasks.

Distributed algorithms (or: protocols) range from algorithms for communication to algorithms for distributed computations. These algorithms in a distributed system appear to be conceptually far more complex than in a single processing unit environment. With a single processing unit only one action can occur at a time, while in a distributed system the number of possibilities of what can happen when and where at a time tends to be enormous, and our human minds are just not able to keep track of all of them.

This leads to the problem of determining whether the executions of a distributed algorithm indeed have the desired effect in all possible circumstances and combinations of events. Testing algorithms has now become completely infeasible: some form of “verification” is the only way out.