What is a Distributed Algorithm?

A distributed algorithm is a specific type of algorithm used on computer software that must use various, interconnected processors. The distributed algorithm is responsible for running different parts of the algorithm at the same time, each on a different processor. The processors must then communicate with each other for the software to run properly.

To understand the distributed algorithm, it's easiest to examine what a typical algorithm is. An algorithm is a defined process that outlines from start to finish the steps that must be taken to complete the desired process or solve a problem. For example, an algorithm for mailing a letter would go something along the lines of:

1. Get envelope
2. Open envelope
3. Insert letter
4. Close envelope
5. Attach stamp

This would continue until the process has been completed. Certain steps may branch off into other steps. These would tell the person what to do if he could not complete one of the main steps and would eventually lead him back to the original algorithm. The important thing is that the algorithm must eventually have an end no matter which path the person takes to reach it.

Technically anything that is a defined process can be an algorithm, such as the above example for mailing a letter. A computer algorithm is an algorithm designed to tell the computer what to do. It has a beginning and an ending step with several steps in between. It helps the computer perform an action and instructs it what to do if something goes wrong. If a file the computer needs is missing, it might instruct it to skip that step or perform an alternate step in its place.

The difference between an algorithm and a distributed algorithm is simply that the distributed algorithm is designed to run on separate processors while a regular computer algorithm would not be. Each processor is performing a different part of the overall algorithm at the same time and then submitting the results.

There are several problems that occur when using distributed algorithms. One of the processors could fail, causing that part of the algorithm to stop working. There could also be a communication problem between processors which would keep the distributed algorithm from reaching the end of the process. Many programmers study distributed algorithms to find out ways to overcome these problems and ensure the algorithm is completed even if there is a technical error.