分散式算法

分散式算法是設計用於在由互連處理器構造的計算機硬體上運行的算法。分散式算法用於分散式計算的許多不同套用領域，例如電信，科學計算，分散式信息處理和實時過程控制。分散式算法解決的標準問題包括領導者選舉，共識，分散式搜尋，生成樹生成，互斥和資源分配。

基本介紹

• 中文名：分散式算法
• 外文名：Distributed algorithm

介紹

分散式算法是並行算法的子類型，通常同時執行，算法的單獨部分在獨立處理器上同時運行，並且關於算法的其他部分正在做什麼的信息有限。開發和實現分散式算法的主要挑戰之一是在面對處理器故障和不可靠的通信鏈路時成功協調算法的獨立部分的行為。選擇合適的分散式算法來解決給定問題取決於問題的特徵和算法運行的系統特性，例如處理器或鏈路故障的類型和機率，進程間通信的類型可以執行的，以及單獨進程之間的定時同步級別。

為分散式計算而設計，它運行在一群相互連結的處理器所構成的計算機硬體平台上。分散式算法以並行方式執行，是平行算法下的子類別。因為同時運行在不同處理器上，對算法其他部份運行情況的資訊所知有限，使得這類型的算法較為困難。

標準問題

原子提交

原子提交是一組操作，其中一組不同的更改作為單個操作套用。如果原子提交成功，則表示已套用所有更改。如果在完成原子提交之前發生故障，則“commit”將中止，並且不會套用任何更改。

用於解決原子提交協定的算法包括兩階段提交協定和三階段提交協定。

共識

共識算法試圖解決許多同意共同決策的過程的問題。

更準確地說，共識協定必須滿足以下四個正式屬性。

終止：每個正確的過程決定一些價值。

有效性：如果所有過程提出相同的值v，則每個正確的過程決定v。

完整性：每個正確的過程最多決定一個值，如果它決定某個值v，那么v必須由某個過程提出。

協定：如果正確的過程決定v，那么每個正確的過程決定v。

解決共識的典型算法是paxos算法。

分散式搜尋

領導者選舉是將單個流程指定為在若干計算機（節點）之間分配的某個任務的組織者的過程。在任務開始之前，所有網路節點都不知道哪個節點將充當任務的“領導者”或協調者。然而，在運行了領導者選舉算法之後，整個網路中的每個節點都將特定的唯一節點識別為任務領導者。

可靠的廣播

可靠廣播是分散式系統中的通信原語。可靠的廣播由以下屬性定義：

有效性 - 如果正確的進程傳送訊息，那么一些正確的進程最終將傳遞該訊息。

協定 - 如果正確的流程傳遞了訊息，那么所有正確的流程最終都會傳遞該訊息。

完整性 - 每個正確的流程最多只傳遞一次相同的訊息，並且只有在流程傳送了該訊息時才會傳遞。

可靠的廣播可以具有順序，因果或總排序。