Distributed algorithms

From Wikipedia, the free encyclopedia

Please help improve this article or section by expanding it.
Further information might be found on the talk page or at requests for expansion. (July 2007)

A distributed algorithm is an algorithm that tries to solve a typical problem in distributed computing.

Here is a list of distributed algorithms by problem:

1 Leader Election
2 Consensus
3 Atomic commit
4 Reliable Broadcast
5 Replication
6 External links

[edit] Leader Election

[edit] Consensus

Consensus Algorithms try to solve the problem of a number of processes agreeing on a common decision. More precisely, a Consensus protocol must satisfy the four formal properties below.

Termination: every correct process decides some value.
Validity: if all processes propose the same value $v$ , then every correct process decides $v$ .
Integrity: every correct process decides at most one value, and if it decides some value $v$ , then $v$ must have been proposed by some process.
Agreement: if a correct process decides $v$ , then every correct process decides $v$ .

A typical algorithm for solving consensus is the paxos algorithm.

An atomic commit is an operation where a set of distinct changes is applied as a single operation. If the atomic commit succeeds, it means that all the changes have been applied. If there is a failure before the atomic commit can be completed, the "commit" is aborted and no changes will be applied. Algorithms for solving the atomic commit protocol include the two-phase commit protocol and the three-phase commit protocol.

[edit] Reliable Broadcast

Reliable broadcast is a communication primitive in distributed systems. A reliable broadcast is defined by the following properties:

validity - if a correct process sends a message, then some correct process will eventually deliver that message
agreement - if a correct process delivers a message, then all correct processes eventually deliver that message
integrity - every correct process delivers the same message at most once and only if that message has been sent by a process

A reliable broadcast can have sequential, causal or total ordering.