Distributed algorithm: Difference between revisions

Revision as of 07:49, 31 May 2009

Revision as of 23:43, 20 July 2009

Line 1:

{{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 variousmany 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 (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|publisher=Morgan Kaufman Publishers|___location=San Francisco, CA|date=1997|edition=1st|isbn=978-1558603486}}</ref>

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