World Library  
Flag as Inappropriate
Email this Article

Distributed algorithm

Article Id: WHEBN0003367202
Reproduction Date:

Title: Distributed algorithm  
Author: World Heritage Encyclopedia
Language: English
Subject: Brooks–Iyengar algorithm, Cannon's algorithm, Distributed minimum spanning tree, HS algorithm, Superstabilization
Collection: Distributed Algorithms
Publisher: World Heritage Encyclopedia
Publication
Date:
 

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 a sub-type of parallel algorithm, 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 1
  • References 2
  • Further reading 3
  • External links 4

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
Non-blocking data structures
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 (1996). Distributed Algorithms. San Francisco, CA:  

Further reading

  • C. Rodríguez, M. Villagra and B. Barán, Asynchronous team algorithms for Boolean Satisfiability, Bionetics2007, pp. 66–69, 2007.

External links

  • MIT Open Courseware - Distributed Algorithms
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
 
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
 
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.
 


Copyright © World Library Foundation. All rights reserved. eBooks from Project Gutenberg are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.