Distributed algorithms

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 $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.

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

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.

Игры ⚽ Поможем сделать НИР

Look at other dictionaries:

Distributed computing — is a field of computer science that studies distributed systems. A distributed system consists of multiple autonomous computers that communicate through a computer network. The computers interact with each other in order to achieve a common goal … Wikipedia
Distributed algorithm — A distributed algorithm is an algorithm designed to run on computer hardware constructed from interconnected processors. Distributed algorithms are used in many varied application areas of distributed computing, such as telecommunications,… … Wikipedia
Distributed minimum spanning tree — The distributed minimum spanning tree problem involves the construction of a minimum spanning tree by a distributed algorithm, in a network where nodes communicate by message passing. It is radically different from the classical sequential… … Wikipedia
Distributed constraint optimization — (DCOP or DisCOP) is the distributed analogue to constraint optimization. A DCOP is a problem in which a group of agents must distributedly choose values for a set of variables such that the cost of a set of constraints over the variables is… … Wikipedia
Distributed web crawling — is a distributed computing technique whereby Internet search engines employ many computers to index the Internet via web crawling. Such systems may allow for users to voluntarily offer their own computing and bandwidth resources towards crawling… … Wikipedia
Distributed Garbage Collection — (DGC) in computing is a particular case of Garbage Collection where references to an object can be held by a remote client. DGC algorithms typically rely on a time lease set on the Object; it s the Remote Client s stub object task to periodically … Wikipedia
Distributed operating system — A distributed operating system is the logical aggregation of operating system software over a collection of independent, networked, communicating, and spatially disseminated computational nodes.[1] Individual system nodes each hold a discrete… … Wikipedia
Distributed hash table — A distributed hash table (DHT) is a class of a decentralized distributed system that provides a lookup service similar to a hash table; (key, value) pairs are stored in a DHT, and any participating node can efficiently retrieve the value… … Wikipedia
Distributed key generation — For some protocols no party should be in the sole possession of the secret key. Rather, during distributed key generation every party obtains a share of the key. A threshold of the participating parties need to cooperate in order to achieve a… … Wikipedia
Distributed control system — Part of a series of articles on Industry Manufacturing methods Batch production • Job production Continuous production Improvement method … Wikipedia

Academic Dictionaries and Encyclopedias

Distributed algorithms

Look at other dictionaries:

Share the article and excerpts

Academic Dictionaries and Encyclopedias

Wikipedia

Distributed algorithms

Look at other dictionaries:

Share the article and excerpts

Direct link