- Distributed algorithms
A distributed algorithm is an
algorithm that tries to solve a typical problem indistributed computing .Here is a list of distributed algorithms by problem:
Leader Election
= 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 , then every correct process decides .
* Integrity: every correct process decides at most one value, and if it decides some value , then must have been proposed by some process.
* Agreement: if a correct process decides , then every correct process decides .A typical algorithm for solving consensus is the
paxos algorithm .Atomic commit 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 thethree-phase commit protocol .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.Replication
ROWA, ROWAA, QA
External links
* [http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Computer-Science/6-852JFall-2005/CourseHome/index.htm MIT's Open Course - Distributed Algorithms]
Wikimedia Foundation. 2010.