分散アルゴリズムのソースを表示

'''分散アルゴリズム'''（ぶんさんアルゴリズム、{{lang-en|Distributed algorithm}}）とは、相互接続された[[プロセッサ]]により構成される[[ハードウェア]]上で実行するために設計された[[アルゴリズム]]である。分散アルゴリズムは[[分散コンピューティング]]の多くの応用分野において使われ、その例として、[[通信]]、科学計算、分散[[情報処理]]、リアルタイム[[プロセス管理]]などがある。分散アルゴリズムによって解決された標準的な問題として、[[リーダー選出]]、[[合意_(情報工学)|合意]]、分散[[探索|検索]]、[[全域木]]生成、[[ミューテックス]]、リソース割り当てなどがある<ref name="lynch1997">{{cite book|last=Lynch|first=Nancy|title=Distributed Algorithms|publisher=[[Morgan Kaufmann Publishers]]|location=San Francisco, CA|date=1997|edition=1st|isbn=978-1558603486}}</ref><ref>増澤利光、山下雅史：「適応的分散アルゴリズム」、共立出版、ISBN 978-4-320-12251-2 (2010年6月30日)</ref>。

典型的な分散アルゴリズムは、[[並列処理|並列]]に実行され、アルゴリズムの各部が独立したプロセッサ上で同時に実行され、アルゴリズムの他の部分については限定的な情報しか持たない。分散アルゴリズムを開発し、実装する上での大きな課題となるのが、プロセッサ障害が発生し、通信接続が不確実であるような環境において、アルゴリズムの独立した部分の動作を統制することである。与えられた問題に対し、適切な分散アルゴリズムを選択することは、問題の特徴と、アルゴリズムが実行されるシステムの特徴の両方に依存する。ここでシステムの特徴とは、プロセッサの性能や、通信接続の障害、可能なプロセス間通信の種類、プロセス間の同期を行う際の精度などを指す<ref name="lynch1997"/>。

== 標準的な問題 ==
; [[アトミックコミット]]
:アトミックコミットとは異なる変更の集合が一つの処理として実行されるような処理のことである。もしアトミックコミットが成功すれば、全ての変更が実行されたことを意味する。もしアトミックコミットが完了するまでに障害があった場合、"コミット"が中止され、どの変更も実行されない。
:アトミックコミットプロトコルを実現するアルゴリズムとして、[[2相コミット]]プロトコルおよび、[[3相コミット]]プロトコルがある。

; [[合意_(情報工学)|合意]]
:合意アルゴリズムはいくつかのプロセスが共通の決定に合意する問題を解くものである。
:より詳細には、合意プロトコルは以下の4つの特徴を備えなければならない。

:* '''終了''': 全ての正常なプロセスはある値を決定する。
:* '''有効性''': もし全てのプロセスが同じ値<math>v</math>を提案する場合、全ての正常なプロセスは<math>v</math>を決定する。
:* '''整合性''': 全ての正常なプロセスは最大1つの値を決定し、もし値<math>v</math>を決定した場合は、<math>v</math>が他のプロセスによって提案されている。
:* '''合意''': もし正常なプロセスが<math>v</math>を決定した場合、すべての正常なプロセスは<math>v</math>を決定する。

:[[Paxosアルゴリズム]]は、合意を実現するための典型的なアルゴリズムである。

; 分散情報検索

; [[リーダー選出]]

; [[ミューテックス]]

; 信頼性のあるブロードキャスト

: 信頼性のあるブロードキャストとは、分散システムにおける通信の基本要素である。以下の特徴によって定義されるものである:

;* '''有効性''' - 正常なプロセスがメッセージを送信するならば、ある正常なプロセスがいずれそのメッセージを伝送する
;* '''合意''' - 正常なプロセスがメッセージを伝送するならば、全ての正常なプロセスがいずれそのメッセージを伝送する
;* '''整合性''' - 全ての正常なプロセスが同じメッセージを最大1回伝送し、それはあるプロセスによりそのメッセージが送信された場合だけである

; [[レプリケーション]]
; [[リソース割り当て]]
; [[全域木]]生成

== 脚注 ==
{{reflist}}

== 外部リンク ==
*[http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Computer-Science/6-852JFall-2005/CourseHome/index.htm MIT's Open Course - Distributed Algorithms] 
{{アルゴリズム}}

[[Category:分散アルゴリズム|*ふんさんあるこりすむ]]