Distributed algorithm

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, scientific computing, distributed information processing, and real-time process control. Standard problems solved by distributed algorithms include leader election, consensus, distributed search, spanning tree generation, mutual exclusion, and resource allocation.[1]

Distributed algorithms are typically executed 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.[1]

Contents

Standard problems

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.
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.
Distributed search
Leader election
Leader election is the process of designating a single process as the organizer of some task distributed among several computers (nodes). Before the task is begun, all network nodes are unaware which node will serve as the "leader," or coordinator, of the task. After a leader election algorithm has been run, however, each node throughout the network recognizes a particular, unique node as the task leader.
Mutual exclusion
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
Resource allocation
Spanning tree generation
Symmetry breaking, e.g. vertex coloring

References

  1. ^ a b Lynch, Nancy (1997). Distributed Algorithms (1st ed.). San Francisco, CA: Morgan Kaufmann Publishers. ISBN 978-1558603486. 

Further reading

External links


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 Coordination Function — (DCF) is the fundamental MAC technique of the IEEE 802.11 wireless LAN standard. DCF employs a CSMA/CA distributed algorithm and an optional virtual carrier sense using RTS and CTS control frames. DCF requires a station wishing to transmit to… …   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 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 = Consensus Algorithms try to solve the problem of a number of …   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 shared memory — (DSM), in Computer Architecture is a form of memory architecture where the (physically separate) memories can be addressed as one (logically shared) address space. Here, the term shared does not mean that there is a single centralized memory but… …   Wikipedia

  • distributed.net — URL distributed.net Type of site volunteer computing Owner Distributed Computing Te …   Wikipedia

  • Distributed algorithmic mechanism design — (DAMD) is an extension of algorithmic mechanism design. DAMD differs from Algorithmic mechanism design since the algorithm is computed in a distributed manner rather than by a central authority. This greatly improves computation time since the… …   Wikipedia

  • Distributed coordination function — (DCF) is the fundamental MAC technique of the IEEE 802.11 based WLAN standard. DCF employs a CSMA/CA with binary exponential backoff algorithm. DCF requires a station wishing to transmit to listen for the channel status for a DIFS interval. If… …   Wikipedia

  • Algorithm — Flow chart of an algorithm (Euclid s algorithm) for calculating the greatest common divisor (g.c.d.) of two numbers a and b in locations named A and B. The algorithm proceeds by successive subtractions in two loops: IF the test B ≤ A yields yes… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”