Distributed algorithm: Difference between revisions

Revision as of 13:27, 10 January 2009

Latest revision as of 20:30, 23 June 2025

(57 intermediate revisions by 49 users not shown)

Line 1:

{{Short description|Algorithm run on hardware built from interconnected processors}}

{{Expand|date=July 2007}}

A '''distributed algorithm''' is an [[algorithm]] designed to run on [[computer hardware]] constructed from interconnected [[cpuCentral processing unit|processors]]. Distributed algorithms are used in variousdifferent application areas of [[distributed computing]], such as [[telecommunications]], [[scientific computing]], distributed [[Data processing|information processing]], and real-time [[process control]]. Standard problems solved by distributed algorithms include [[leader election]], [[Consensus (computer science)|consensus]], distributed [[Search algorithm|search]], [[Spanning tree (mathematics)|spanning tree]] generation, [[mutual exclusion]], and [[resource allocation]].<ref name="lynch1997">{{cite book|last=Lynch|first=Nancy|title=Distributed Algorithms|url=https://archive.org/details/distributedalgor0000lync|url-access=registration|publisher=[[Morgan KaufmanKaufmann Publishers]]|___location=San Francisco, CA|dateyear=1997|edition=1st1996|isbn=978-15586034861-55860-348-6}}</ref>

Distributed algorithms are a sub-type of [[parallel algorithm]], 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"/>

A '''distributed algorithm''' is an [[algorithm]] designed to run on [[computer hardware]] constructed from interconnected [[cpu|processors]]. Distributed algorithms are used in various 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 (computer science)|consensus]], distributed search, [[spanning tree]] generation, [[mutual exclusion]], and [[resource allocation]].<ref name="lynch1997">{{cite book|last=Lynch|first=Nancy|title=Distributed Algorithms|publisher=Morgan Kaufman Publishers|___location=San Francisco, CA|date=1997|edition=1st|isbn=978-1558603486}}</ref>

== Standard problems ==

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"/>

; [[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.

=== [[Leader election|Leader Election]] ===

:Algorithms for solving the atomic commit protocolproblem include the [[two-phase commit protocol]] and the [[three-phase commit protocol]].

===; [[Consensus (computer science)|Consensus]] ===

:Consensus Algorithmsalgorithms 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.

:* '''TerminationValidity''': if all processes propose the same value <math>v</math>, then every correct process decides some value<math>v</math>.

:* '''ValidityIntegrity''': ifevery allcorrect processesprocess decides proposeat themost sameone value, and if it decides some value <math>v</math>, then every correct process decides <math>v</math> must have been proposed by some process.

:* '''IntegrityAgreement''': everyif a correct process decides at most one value, and if it decides some value <math>v</math>, then every correct process decides <math>v</math> must have been proposed by some process.

:Common algorithms for solving consensus are the [[Paxos algorithm]] and the [[Raft (computer science)|Raft algorithm]].

* '''Agreement''': if a correct process decides <math>v</math>, then every correct process decides <math>v</math>.

; Distributed search

===; [[Leader election|Leader Election]] ===

A typical algorithm for solving consensus is the [[paxos algorithm]].

: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 of 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.

===; [[AtomicMutual commitexclusion]] ===

; [[Non-blocking data structures]]

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.

;[[Terminating Reliable Broadcast|Reliable Broadcast]]

Algorithms for solving the atomic commit protocol include the [[two-phase commit protocol]] and the [[three-phase commit protocol]].

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

=== Reliable Broadcast ===

:* '''Agreement''': - if a correct process decidesdelivers <math>v</math>a message, then everyall correct processprocesses eventually deliver decidesthat <math>v</math>message.

:* '''Integrity''' - every correct process delivers the same message at most once and only if that message has been sent by a process.

Reliable broadcast is a communication primitive in distributed systems. A reliable broadcast is defined by the following properties:

:A reliable broadcast can have sequential, causal or total ordering.

; [[Replication (computer science)|Replication]]

* '''Validity''' - if a correct process sends a message, then some correct process will eventually deliver that message

; [[Resource allocation]]

* '''Agreement''' - if a correct process delivers a message, then all correct processes eventually deliver that message

; [[Spanning tree]] generation

* '''Integrity''' - every correct process delivers the same message at most once and only if that message has been sent by a process

; Symmetry breaking, e.g. [[vertex coloring]]

A reliable broadcast can have sequential, causal or total ordering.

=== Replication ===

ROWA, ROWAA, QA

== References ==

{{reflist}}

== ExternalFurther linksreading ==

* {{citation|author1=Christian Cachin |author2=Rachid Guerraoui |author3=Luís Rodrigues |title=Introduction to Reliable and Secure Distributed Programming| publisher=Springer| year=2011|bibcode=2011itra.book.....C | isbn=978-3-642-15259-7| edition=2.}}

*[http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Computer-Science/6-852JFall-2005/CourseHome/index.htm MIT's Open Course - Distributed Algorithms] <!-- material here should eventually be absorbed into this article -->

*C. Rodríguez, M. Villagra and B. Barán, {{doi-inline|10.1109/BIMNICS.2007.4610083|Asynchronous team algorithms for Boolean Satisfiability}}, Bionetics2007, pp.&nbsp;66–69, 2007.

==External links==

*{{Commonscatinline|Distributed algorithms}}

*[http://ocw.mit.edu/OcwWebcourses/Electricalelectrical-Engineeringengineering-and-Computercomputer-Sciencescience/6-852JFall852j-2005/CourseHomedistributed-algorithms-fall-2009/index.htm MIT's Open CourseCourseware - Distributed Algorithms] <!-- material here should eventually be absorbed into this article -->

[[Category{{DEFAULTSORT:Distributed computing]]Algorithms}}

[[Category:Distributed algorithms|* ]]