Distributed Computing: Models and Methods

Distributed computing is an activity that is performed on a spatially distributed system. An important problem in distributed computing is to provide a user with a non-distributed view of a distributed system to implement a distributed file system that allows the client programmer to ignore the physical location of his data. The models of computation generally considered to be distributed are process models in which the computational activity is represented as the concurrent execution of sequential processes. Different process models are distinguished by the mechanism employed for inter-process communication. The process models that are most distributed are the ones in which processes communicate by message passing. A process sends a message by adding it to a message queue and another process receives the message by removing it from the queue. There are two basic complexity measures for distributed algorithms: time and message complexity. The time complexity of an algorithm measures the time needed both for message transmission and for computation within the processes. The most common measure of message complexity is the total number of messages transmitted. If messages contain on the order of a few hundred bits or more, then the total number of bits sent might be a better measure of the cost than the number of messages.