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:
Leader Election
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.
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 protocolok.
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