Content deleted Content added
further flesh out the lead |
Convert to definition list |
||
Line 5:
Distributed algorithms are typically executed [[concurrency (computer science)|concurrently]], with separate parts of the algorithm being run simultaneously on independent processors, and having limited information about what the other parts of the algorithm are doing. One of the major challenges in developing and implementing distributed algorithms is successfully coordinating the behavior of the independent parts of the algorithm in the face of processor failures and unreliable communications links. The choice of an appropriate distributed algorithm to solve a given problem depends on both the characteristics of the problem, and characteristics of the system the algorithm will run on such as the type and probability of processor or link failures, the kind of inter-process communication that can be performed, and the level of timing synchronization between separate processes.<ref name="lynch1997"/>
== Standard problems ==
=== [[Leader election|Leader Election]] ===▼
: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]].▼
:Consensus
: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 <math>v</math>, then every correct process decides <math>v</math>.
:* '''Integrity''': every correct process decides at most one value, and if it decides some value <math>v</math>, then <math>v</math> must have been proposed by some process.
:* '''Agreement''': if a correct process decides <math>v</math>, then every correct process decides <math>v</math>.
:A typical algorithm for solving consensus is the [[paxos algorithm]].
; Distributed search
▲=== [[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 the [[three-phase commit protocol]].
=== Reliable Broadcast ===▼
; Mutual exclusion
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▼
▲:Reliable broadcast is a communication primitive in distributed systems. A reliable broadcast is defined by the following properties:
* '''Integrity''' - every correct process delivers the same message at most once and only if that message has been sent by a process▼
▲:* '''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.
; Resource allocation
; Spanning tree generation
== References ==
| |||