簡化的Paxos算法的製作方法
2023-06-14 08:59:46
專利名稱：簡化的Paxos算法的製作方法
技術領域：
本發明一般涉及分布式計算，尤其涉及使用少量計算裝置的有效故障容錯分布式計算。
背景技術：
當個人計算裝置變得越來越功能強大，包含增加的存儲空間和處理能力時，普通用戶在執行日常任務時消耗那些資源的越來越小的百分比。由此，許多當今的個人計算裝置通常未充分利用其完全的潛在能力，因為其計算能力很大程度上超出大多數用戶對它們的要求。從強大的現代個人計算裝置的未使用資源中得出使用和價值的一種越來越普及的方法是分布式計算系統，其中，計算裝置彼此協作地運作，以提供對數據和計算資源的更可靠的訪問。
除提供用於使用超出的計算能力的有用機制以外，分布式系統也能夠由專用廉價計算裝置組成，以達到更大、更昂貴的計算裝置的性能和存儲能力。分布式系統的另一優點是在面對會削弱單個、較大的計算裝置的具體困難時仍能夠繼續操作的能力。這類困難可包括持續不變的電源儲能損耗、嚴酷的天氣、洪水、恐怖活動等等。
為補償單個計算裝置會從網絡上斷開連接、關閉、遭受系統故障或變得不能使用等增加的風險，可使用冗餘度來允許分布式計算系統保持可操作。由此，儲存在任何一個個人計算裝置上的信息可被冗餘地儲存在至少一個另外的個人計算裝置上，從而，即使個人計算裝置之一發生故障，仍允許信息保持可訪問。
分布式計算系統可實現完全的冗餘度，因為系統中的每一裝置執行相同的任務並儲存相同的信息。這一系統可允許用戶即使在除一個裝置之外的所有裝置都發生故障時，也能夠繼續執行有用的操作。可選地，這一系統可用於允許同一信息的多個副本遍及一個地理區域分布。例如，多國組織可建立一種全球範圍的分布式計算系統。
然而，分布式系統很難維護，這是由於正確地同步構成該系統的各個裝置的複雜性。由於在各個進程上計時是最困難的，因此通常使用一種狀態機方法來協調各個裝置之間的活動。狀態機可由一組狀態、一組命令、一組響應和將每一響應/狀態對連結到每一命令/狀態對的客戶機命令來描述。狀態機可通過改變其狀態並產生響應來執行命令。由此，狀態機可由其當前狀態和它將要執行的行動的完整地描述，從而無需使用精確的計時。
因此，狀態機的當前狀態取決於其前一狀態、自從那時以來所執行的命令以及執行那些命令的順序。為保持兩個或多個狀態機之間的同步，可建立一公用初始狀態，並且每一狀態機可從該初始狀態開始，以同樣的順序執行同樣的命令。因此，為將一個狀態機與另一個同步，需要確定由其它狀態執行的命令。因此，同步問題變為確定執行命令的順序的問題，或者更具體地，變為確定對給定的步驟所執行的特定命令的問題。
用於確定對給定的步驟執行了哪一命令的一種機制被稱為Paxos算法。在Paxos算法中，各個裝置的任一個可擔當領導者，並試圖提議由系統中每一裝置執行的一給定客戶機命令。每一這樣的提議可連同一提議號一起發送，以便更容易地跟蹤該提議。這些提議號不需要負擔與裝置試圖對命令達成一致來執行的特定步驟的關係。最初，領導者可對領導者意圖提交的提議建議一提議號。然後，剩餘裝置的每一個可用它們投票贊成的最後一個提議的指示，或它們不投票贊成任何提議的指示來響應領導者對提議號的建議。如果領導者通過各種響應未獲悉由那些裝置投票贊成的任何其它提議，則領導者可使用在較早的消息中建議的提議號來提議給定的客戶機命令由那些裝置執行。在那一階段，每一裝置可確定是投票贊成該行動還是拒絕它。裝置應當僅在它響應另一領導者對不同提議號的建議時才能拒絕行動。如果被稱為法定人數(quorum)的足夠數量的裝置投票贊成該提議，則認為所提議的行動被達成一致，並且每一裝置執行該行動，並可發送結果。以這一方式，每一裝置可以同樣的順序執行行動，從而保持所有裝置之間的相同的狀態。
一般而言，Paxos算法可被認為有兩個階段-如上所述允許領導者獲悉由裝置投票贊成的先前提議的初始階段，以及領導者可提議用於執行的客戶機命令的第二階段。一旦領導者獲悉先前提議，它不需要不斷地重複第一階段。相反，領導者可不斷地重複第二階段，提議可由分布式計算系統在多個步驟中執行的一系列客戶機命令。以這一方式，儘管由分布式計算系統對每一步驟所執行的每一客戶機命令可被認為是Paxos算法的一個實例，然而領導者在提議下一步驟的另一客戶機命令之前無需等候裝置投票贊成給定步驟的所提議的客戶機命令。
作為一個整體，分布式計算系統可被模型化為一狀態機。由此，實現完全的冗餘度的分布式計算系統可令每一裝置複製整個系統的狀態。這一系統需要每一裝置維持同一狀態。如果某些裝置認為已執行了一個客戶機命令，而第二組裝置認為已執行了一個不同的客戶機命令，則整個系統不再作為單個狀態機來運作。為避免這一情況，一般要求大部分裝置選擇一個提議的客戶機命令由系統執行。由於其每一個都具有眾多裝置的任何兩個裝置組必須共享至少一個裝置，因此諸如Paxos算法等機制可被實現為依賴於至少一個公用裝置，以防止其每一個都包含眾多裝置的兩個組選擇不同的所提議的客戶機命令。
然而，Paxos算法會添加在客戶機發送要由分布式系統執行命令的請求時刻和在客戶機從該命令的執行接收結果時刻之間的消息延遲。特別地，即使客戶機向領導者發送請求，並且即使領導者已獲悉先前所投票贊成的提議，並由此已完成了Paxos算法的第一階段，然而在從客戶機發送請求和向客戶機發送結果之間仍有兩個或多個消息延遲。
發明內容
因此，在本發明的一個實施例中，一種具有較少量裝置的故障容錯系統能夠實現一種更有效的Paxos算法，並能夠在從客戶機發送請求和向客戶機發送結果之間引入少至單個的消息延遲。
在另一實施例中，提出了一種更有效的Paxos算法，其中，領導者可同時發送兩種類型的第二階段消息，從而允許接收計算裝置確定請求的執行結果而不會引入額外的消息延遲。
在又一實施例中，領導者計算裝置不需要是獲悉者，從而允許分布式計算系統中的其它計算裝置更快速地獲悉所執行的命令的結果。另外，不參與更有效Paxos算法的執行的計算裝置也可以是獲悉者，客戶機計算裝置也可以是獲悉者。
在再一實施例中，參與更有效Paxos算法的執行的計算裝置中的至少一個計算裝置可以是廉價的計算裝置，它可能具有有限的計算和存儲器存儲能力。
儘管本發明的描述主要集中在分布式計算系統中的計算裝置的操作上，然而可以理解，本描述也可同等地適用於運行在單個計算裝置上的進程，如在單獨的處理器上或在單獨的存儲器空間中。由此，另外的實施例包括在多處理器環境中更有效Paxos算法的操作，不論多個處理器是物理地位於一個還是多個計算裝置中；也包括在多個虛擬機器環境中的操作，不論多個虛擬機器是由一個還是多個計算裝置執行。當參考附圖閱讀以下說明性實施例的詳細描述時，可以清楚本發明的另外的特徵和優點。
儘管所附權利要求書以細節闡明了本發明的特徵，然而當結合附圖閱讀以下詳細描述時，可以最好地理解本發明及其目的和優點，附圖中圖1是一般示出了可實現本發明的一個實施例的示例性分布式計算系統的框圖；圖2是一般示出了可實現本發明的一個實施例的示例性計算裝置的框圖；圖3a-e一般示出了本發明的一個實施例考慮的意見一致算法的操作；圖4a-g一般示出了本發明的一個實施例考慮的多步驟意見一致算法的操作；圖5a-c一般示出了本發明的一個實施例考慮的多步驟意見一致算法的縮略版本的操作；圖6a-c一般示出了本發明的一個實施例考慮的多步驟意見一致算法的縮略版本的操作；圖7a-b一般示出了本發明的一個實施例考慮的簡化的意見一致算法的操作；圖8a-b一般示出了本發明的一個實施例考慮的另一簡化的意見一致算法的操作；圖9a-b一般示出了本發明的一個實施例考慮的用廉價裝置的簡化的意見一致算法的操作；圖10a-b一般示出了本發明的一個實施例考慮的用廉價裝置的簡化的意見一致算法的進一步操作；圖11a-b一般示出了本發明的一個實施例考慮的用廉價裝置的另一簡化的意見一致算法的操作；圖12一般示出了本發明的一個實施例考慮的用廉價裝置的另一簡化的意見一致算法的進一步操作；圖13a-b一般示出了本發明的一個實施例考慮的用廉價裝置的又一簡化的意見一致算法的操作。
具體實施例方式
分布式計算系統可包括眾多個別的個人計算裝置、伺服器計算裝置或具有足夠的處理器和存儲能力來參與該系統的其它裝置。分布式計算系統可集合其構成計算裝置的能力來提供大為提高的處理能力或存儲空間，或實現冗餘度，從而允許多個裝置提供對同一信息的訪問。由此，分布式計算系統的一個常見使用是將連接到公共網絡的許多不同的個人計算裝置的未使用的處理能力和存儲空間集合起來。這一分布式系統可維護關於該系統的信息，如哪些裝置當前是系統的一部分，以及給定的信息集儲存在哪一裝置上。這些信息可以對裝置是必須的，以集合其能力和存儲空間，並且作為結果，每一裝置可包含一個副本。系統的裝置之間的信息的同步可通過如下文所描述的狀態機方法來便於實現。
可選地，分布式計算系統的一個越來越常見的使用是可擔當各種形式的信息的中央存儲庫的網絡伺服器。這一分布式系統試圖將中央存儲複製到其所有的構成裝置上，使得試圖與中央存儲通信的每一客戶機可找出與其通信的方便且有效的裝置。此外，由於系統的分布式特性，諸如能量儲能消耗、洪水、政治動蕩等本地事件可以只影響少數計算裝置，從而允許整個系統繼續正確地操作，並向客戶機提供對信息和其它服務的訪問。
這一分布式計算系統可被認為是一種狀態機，該機器的未來狀態由當前狀態以及要求採取的行動來定義。分布式計算系統的每一構成裝置然後可獨立地執行整個系統的狀態機。狀態機方法可被異步地實現；使得不需要維持構成裝置上的精確同步，並且裝置之間的同步可通過對所有的裝置設置一初始狀態，然後以相同的順序執行相同的功能來實現。維持同步的一種常見的方法是允許分布式計算系統的構成裝置在執行下一功能前都對該功能達成一致，並維護所執行的功能的列表。以這一方式，每一裝置可具有相同的狀態，如果一個裝置發生故障，則僅需要確定所它所執行的最後一個任務、從列表標識自從最後一個任務以來所達成一致的任何功能、並執行那些功能。
擔當伺服器的分布式計算系統對向一組各種客戶機供應大量信息的伺服器尤其有用，如用於多國組織的中央資料庫，或流行的全球資訊網站。在這一情況中，大量的客戶機可向擔當伺服器的分布式計算系統請求信息。通過在多個裝置上實現伺服器功能，可並行地服務更多客戶機，由此增加了整個系統的吞吐量，並且由於增加的冗餘度，伺服器作為一個整體更不易於發生故障。
構成計算裝置可用於對要執行的下一功能達成一致的一種機制被稱為Paxos算法。在Paxos算法中，如下文進一步所描述的，任一裝置可擔當領導者，並向分布式計算系統內的其它裝置發送對一提議號的建議。其它裝置可用具有裝置已經投票贊成的最大提議號的提議的指示，或裝置未投票贊成任何先前的協議的指示來響應。一旦領導者從其它裝置接收到響應，它可確定要提議哪一功能，並請求對所提議的功能進行投票。每一裝置將對該提議進行投票，除非它在提議的初始發送之後並在請求投票之前的某一時刻響應了對更高提議號的建議。如果法定人數的裝置投票贊成了該提議，則該提議被接受，並且領導者可向所有裝置發送請求它們執行所達成一致的功能的消息。
然而，Paxos算法在客戶機對請求的接收和向客戶機發送結果之間引入了一系列消息延遲。具體地，在客戶機接收請求之後，並假定先前已完成了Paxos算法的第一階段，並且領導者現在知道要使用的適當的提議號，領導者可使用適當的提議號向執行Paxos算法的其它裝置發送投票請求。這一步驟可引入一個消息延遲。隨後，執行Paxos算法的其它裝置可向領導者返回其投票，這可引入第二個消息延遲。一旦領導者從法定人數的裝置接收到投票，它可指令裝置執行該客戶機請求。同時，領導者本身可執行該客戶機請求並可向客戶機返回結果。由此，不將客戶機和領導者之間的發送計算在內，Paxos算法可在客戶機請求和響應之間引入兩個或多個消息延遲。
如下文將詳細示出的，通過在具有足夠小數量的構成計算裝置的分布式計算環境中組合消息，在客戶機請求和對客戶機的響應之間可消除至少一個消息延遲。
分布式計算環境轉向附圖，其中，相同的標號指相同的元件，示出本發明在一分布式計算系統中實現，如圖1所示的示例性分布式計算系統10。僅為了易於說明，將參考分布式計算系統10來描述本發明，它包括計算裝置11到13，它們如圖1所示地互連在一起。如本領域的技術人員所理解的，本發明適用於所有的分布式計算環境，並且並不試圖以任何方式由圖1的示例性分布式計算系統局限，圖1的系統為說明目的而被簡化。
圖1也示出了單個客戶機裝置20，儘管本發明旨在具有任意數量的客戶機計算裝置的環境中運作。客戶機計算裝置20被示出為具有到分布式計算系統10的通用通信連接。如本領域的技術人員已知的，這一通信連接可使用任何通信媒質和協議，並可允許客戶機計算裝置20與分布式計算系統10中的一個或多個計算裝置進行通信。
另外，圖1示出了計算裝置30和31，它們被示出不是分布式計算系統10的一部分，但是它們仍維持與系統10的通用通信連接。如上所述，通信連接可使用任何通信媒質和協議，並可允許計算裝置30到31與分布式計算系統10中的一個或多個計算裝置進行通信。如下文更詳細地描述的，計算裝置30和31可獲悉由系統10實現的執行的結果，而不必是系統10的一部分。
儘管並非所需，本發明將在諸如由計算裝置執行的程序模塊等計算機可執行指令的一般上下文中描述。一般而言，程序模塊包括例程、程序、對象、組件、數據結構等等，執行特定的任務或實現特定的抽象數據類型。此外，本領域的技術人員可以理解，本發明可以用許多不同的計算裝置來實踐，包括手持式設備、多處理器系統、基於微處理器或可編程消費者電子設備、網絡PC、小型機、大型機等等。如上所述，本發明也可在諸如分布式計算系統10等分布式計算環境中實踐，其中，任務由通過通信網絡連結的遠程處理設備來執行。在分布式計算環境中，程序模塊可以位於本地和遠程存儲器存儲設備中。
轉向圖2，示出了可在其上實現本發明的示例性計算裝置100。計算裝置100僅為合適的計算裝置的一個示例，並非暗示對本發明的使用範圍或功能的局限。例如，示例性計算裝置100並非正好代表圖1所示的計算裝置11-13、20或30-31的任一個。示例性計算裝置100可實現這些計算裝置的一個或多個，如通過存儲器分區、虛擬機器、多處理器、或允許一個物理計算結構如歸於多個計算裝置那樣執行下文描述的行動的類似編程技術。此外，計算裝置100不應當被解釋為對圖2所示的外設的任一個或其組合具有依賴或需求。
本發明可在諸如由計算裝置執行的程序模塊等計算機可執行指令的一般上下文中描述。一般而言，程序模塊包括例程、程序、對象、組件、數據結構等等，執行特定的任務或實現特定的抽象數據類型。在分布式計算環境中，任務可由通過通信網絡連結的遠程處理設備來執行。在分布式計算環境中，程序模塊可以位於本地和遠程計算機存儲媒質中，包括存儲器存儲設備。
計算裝置100的組件可包括但不限於，處理單元120、系統存儲器130以及將包括系統存儲器的各類系統組件耦合至處理單元120的系統總線121。系統總線121可以是若干種總線結構類型的任一種，包括存儲器總線或存儲器控制器、外圍總線以及使用各類總線體系結構的局部總線。作為示例而非局限，這類體系結構包括工業標準體系結構(ISA)總線、微通道體系結構(MCA)總線、增強ISA(EISA)總線、視頻電子技術標準協會(VESA)局部總線以及外圍部件互連(PCI)總線，也稱為Mezzanine總線。此外，處理單元120可包含一個或多個物理處理器。
計算裝置100通常包括各種計算機可讀媒質。計算機可讀媒質可以是可由計算裝置110訪問的任一可用媒質，包括易失和非易失媒質、可移動和不可移動媒質。作為示例而非局限，計算機可讀媒質包括計算機存儲媒質和通信媒質。計算機存儲媒質包括以用於儲存諸如計算機可讀指令、數據結構、程序模塊或其它數據等信息的任一方法或技術實現的易失和非易失，可移動和不可移動媒質。計算機存儲媒質包括但不限於，RAM、ROM、EEPROM、快閃記憶體或其它存儲器技術、CD-ROM、數字多功能盤(DVD)或其它光碟存儲、磁盒、磁帶、磁碟存儲或其它磁存儲設備、或可以用來儲存所期望的信息並可由計算機110訪問的任一其它媒質。通信媒質通常在諸如載波或其它傳輸機制的已調製數據信號中包含計算機可讀指令、數據結構、程序模塊或其它數據，並包括任一信息傳送媒質。術語「已調製數據信號」指以對信號中的信息進行編碼的方式設置或改變其一個或多個特徵的信號。作為示例而非局限，通信媒質包括有線媒質，如有線網絡或直接連線連接，以及無線媒質，如聲學、RF、紅外和其它無線媒質。上述任一的組合也應當包括在計算機可讀媒質的範圍之內。
系統存儲器130包括以易失和/或非易失存儲器形式的計算機存儲媒質，如只讀存儲器(ROM)131和隨機存取存儲器(RAM)132。基本輸入/輸出系統133(BIOS)包括如在啟動時幫助在計算機110內的元件之間傳輸信息的基本例程，通常儲存在ROM 131中。RAM 132通常包含處理單元120立即可訪問或者當前正在操作的數據和/或程序模塊。作為示例而非局限，圖2示出了作業系統134、應用程式135、其它程序模塊136和程序數據137。
計算裝置100也可包括其它可移動/不可移動、易失/非易失計算機存儲媒質。僅作示例，圖2示出了對不可移動、非易失磁媒質進行讀寫的硬碟驅動器141、對可移動、非易失磁碟152進行讀寫的磁碟驅動器151以及對可移動、非易失光碟156，如CD ROM或其它光媒質進行讀寫的光碟驅動器155。可以在示例性操作環境中使用的其它可移動/不可移動、易失/非易失計算機存儲媒質包括但不限於，磁帶盒、快閃記憶體卡、數字多功能盤、數字視頻帶、固態RAM、固態ROM等等。硬碟驅動器141通常通過不可移動存儲器接口，如接口140連接到系統總線121，磁碟驅動器151和光碟驅動器155通常通過可移動存儲器接口，如接口150連接到系統總線121。
圖2討論並示出的驅動器及其關聯的計算機存儲媒質為計算裝置100提供了計算機可讀指令、數據結構、程序模塊和其它數據的存儲。例如，在圖2中，示出硬碟驅動器141儲存作業系統144、應用程式145、其它程序模塊146和程序數據147。注意，這些組件可以與作業系統134、應用程式135、其它程序模塊136和程序數據137相同，也可以與它們不同。這裡對作業系統144、應用程式145、其它程序模塊146和程序數據147給予不同的標號來說明至少它們是不同的副本。用戶可以通過輸入設備，如鍵盤162和定位設備161(通常指滑鼠、跟蹤球或觸摸板)向計算裝置100輸入命令和信息。其它輸入設備(未示出)可包括麥克風、操縱杆、遊戲墊、圓盤式衛星天線、掃描儀等等。這些和其它輸入設備通常通過耦合至系統總線的用戶輸入接口160連接至處理單元120，但是也可以通過其它接口和總線結構連接，如並行埠、遊戲埠或通用串行總線(USB)。監視器191或其它類型的顯示設備也通過接口，如視頻接口190連接至系統總線121。除監視器之外，計算機也包括其它外圍輸出設備，如揚聲器197和印表機196，通過輸出外圍接口195連接。
計算裝置100可以在諸如圖1所示的使用到一個或多個遠程計算機的邏輯連接的網絡化環境中操作。圖2示出了到遠程計算裝置180的通用網絡連接171。通用網絡連接171以及圖1所示的網絡連接可以是各種不同類型的網絡和網絡連接的任一種，包括區域網(LAN)、廣域網(WAN)、無線網絡、符合乙太網協議、令牌環協議的網絡、或其它邏輯、物理或無線網絡，包括網際網路或全球資訊網。
當在網絡化環境中使用時，計算裝置100通過網絡接口或適配器170連接至通用網絡連接171，它們可以是有線或無線網絡接口卡、數據機或類似的連網裝置。在網絡化環境中，描述的與計算裝置100相關的程序模塊或其部分可儲存在遠程存儲器存儲設備中。可以理解，示出的網絡連接是示例性的，也可以使用在計算機之間建立通信的其它裝置。
在以下的描述中，將參考由一個或多個計算裝置執行的行動和操作的符號表示來描述本發明，除非另外指明。由此，可以理解，這類行動和操作，有時稱為計算機執行的，包括計算裝置的處理單元對以結構化形式表示數據的電信號的操縱。這一操縱轉換了數據或在計算裝置的存儲器系統中的位置上維護它，從而以本領域的技術人員都理解的方式重配置或改變了計算機的操作。維護數據的數據結構是存儲器的物理位置，具有由數據的格式所定義的具體特性。然而，儘管在上述的上下文環境中描述本發明，它並不意味著限制，如本領域的技術人員所理解的，後文所描述的行動和操作的各方面也可以硬體實現。
概述依照本發明，在領導者完成了Paxos算法的第一階段之後，或為當前步驟建立了適當的提議號之後，領導者可提交客戶機請求用於投票。連同請求在客戶機請求的執行上進行投票的消息一起，領導者也可發送其對該請求的執行的投票。在具有三個計算裝置的分布式計算環境中，任意兩個這樣的裝置可以是多數和足夠大的法定人數來維護分布式系統的正確操作，只要發生故障的裝置比該系統的大多數裝置少。由於兩個裝置可構成法定人數，當任何其它裝置接收領導者的投票請求以及領導者的投票時，如果該裝置也要對客戶機請求的執行投票，則將存在包括領導者和該其它裝置的法定人數。因此，如果裝置投票贊成客戶機請求的執行，它然後可繼續執行該請求並向客戶機提供結果，而無需等候任何進一步的消息。
如所示的，在三個裝置的系統中，任意兩個裝置形成了法定人數。由此，當領導者發送其自己的投票以及投票請求時，如果其它兩個裝置選擇如領導者所要求地投票，則其任一個可構成法定人數。此外，由於其它兩個裝置已接收了領導者的投票，並且可知曉其自己的投票，因此它們可在不需要等候任何進一步的消息的情況下確定是否有法定人數投票贊成了客戶機請求的執行，並因此在適當時，可執行客戶機請求並向客戶機返回結果，而不會有進一步的消息延遲。
為保存消息或存儲和處理能力，領導者不需要知曉法定人數的投票。由於領導者的投票連同投票請求一起發送，其它裝置可基於領導者的投票及其自己的投票來個別地確定是否有法定人數同意執行客戶機請求。然而，由於沒有明確發送回領導者，領導者可能永遠不會獲悉其它裝置的投票。然而，領導者不需要獲悉法定人數的投票。由此，可向領導者發送指示投票結果的消息，或為了保存消息或保存領導者的存儲或處理能力，領導者不需要接收這一消息。
儘管領導者無需獲悉法定人數的投票，然而除客戶機之外，其它裝置可能希望獲悉客戶機請求的執行的結果。因此，確定應當執行客戶機請求並執行該請求的裝置可向客戶機以及其它計算裝置發送結果。這些其它計算裝置可包括使用Paxos算法來維持分布式計算系統中的冗餘度的裝置，以及不是Paxos算法的一部分的其它裝置，但也可試圖獲悉由系統實現的執行的結果。
由於使用Paxos算法來維持冗餘度的某些裝置，如領導者，不需要獲悉任一特定的投票或客戶機請求的執行的結果，因此這些裝置可用具有有限存儲或處理能力的廉價計算裝置來實現。此外，這類廉價計算裝置可僅在選擇法定人數所需的意義上參與Paxos算法，從而進一步減少了其涉及度，並因此減少了最小所需的處理或存儲能力。
狀態機在諸如圖1所示的分布式系統10的分布式計算環境中，在裝置之間進行協調是一項困難的任務。用於避免內涵在於依賴於時間作為協調因素的困難的一種機制是將分布式計算系統按照狀態機來模型化，其中，功能的執行將狀態機從一個狀態移動到另一個。由此，狀態機可參考一組狀態、一組命令、一組響應和將每一響應/狀態對連結到每一命令/狀態對的功能來描述。狀態機的客戶機可發出請求狀態機執行功能的命令。該功能然後可改變狀態機的狀態並產生響應。
構成分布式計算系統的各個裝置的每一個可執行該系統的狀態機。因此，可通過確定一初始狀態，然後從那時開始以相同的順序執行相同的功能，來協調這些裝置。可通過簡單地確定該裝置所執行的最後一個功能、在由其它裝置執行的已排序功能列表中查找該功能、然後指導裝置執行已排序列表中該裝置尚未執行的功能，來同步裝置。這一狀態機方法最初在Leslie Lamport的文章「Time，Clccks，andthe Ordering of Events in a Distributed System(分布式系統中的時間、時鐘和事件的排序)」中提出，發表在The Communications of the ACM上，卷21，7號，1978年1月，其內容通過引用整體結合於此。
Paxos算法通過使用狀態機方法，圖1所示的分布式系統10的構成裝置11到13的同步可通過對要執行的功能以及執行它們的順序達成一致來實現。用於對要執行的功能達成一致的一種方法被稱為Paxos算法。Paxos算法允許系統10即使在面對故障時也能正確地運作，而通常在這類故障中，裝置會停止運作而不發出任何提前的警告。Paxos算法要求在系統作為整體執行功能之前，裝置的至少法定人數對該功能達成一致。採用Paxos算法，法定人數可以是簡單多數，或可包括更多的裝置，取決於系統的具體要求。不論如何定義，法定人數可足夠大，使得任意兩個法定人數可具有公用的至少一個正確運作的裝置。
為維持一致性，系統10可將功能的執行限制到每步驟一個功能。因此，期望對給定的步驟僅選擇一個功能。由於任意兩個法定人數具有公用的至少一個正確運作的裝置，不多於一個步驟的選擇可通過要求每一裝置僅對一個提議投票來確保。然而，如果若干裝置同時擔當領導者，則這一要求將導致僵局，因為法定人數可能無法對任何提議達成一致，並且沒有一個裝置能夠對不同功能的提議投票使得最終可達到法定數量。
Paxos算法通過一多步驟過程解決了這一問題，該過程允許裝置改變其投票，而領導者仍被限制在它們所提議的功能中。使用Paxos算法，領導者可提議它所選擇的任何功能，除非領導者獲悉先前所提議的功能。如果領導者獲悉法定數量團體的至少一個裝置已投票贊成的至少一個先前所提議的功能，則領導者可提議它所獲悉的先前提議的功能中的最近的一個。每一裝置只需跟蹤該裝置所投票贊成的最近的提議。如果裝置接收到它允諾投票的提議，並且同時它尚未允諾投票贊成另一提議，則裝置可投該提議的票。如果提議具有比該裝置先前允諾投票贊成的任一其它提議更大的提議號，則裝置只能允諾投票該提議。提議號的使用允許系統在不需要採取構成裝置之間的複雜且昂貴的時鐘同步的情況下實現正確的操作。最近的提議一般具有最大的提議號。如果不是，則可忽略該提議，如下文所解釋的。當允諾投票贊成提議時，裝置也可向請求投票的領導者發送最高提議號，它小於該裝置先前允諾投票贊成的當前提議號。以這一方式，領導者總是能夠獲悉先前的提議。
轉向圖3a，使用示例性分布式計算系統10更詳細地解釋了Paxos算法，該系統包括三個裝置11到13，如圖所示。在這一環境中，可將法定人數定義為兩個或多個裝置的任一組，因為這一定義可確保每一法定人數具有至少一個公用的裝置。如圖3a所示，裝置13可假定一領導地位位置，並向裝置11和12發送消息200，建議系統執行給定功能的提議的提議號。由於裝置13既擔當裝置又擔當領導者，它向其自身發送消息200，儘管這一發送可對裝置內部地被處理，並不需要物理地發送。裝置13可選擇任意大的提議號，試圖確保沒有具有更大提議號的先前的提議。此外，由於裝置13本身可對先前的提議投票，它可選擇大於裝置13所知曉的任何提議的提議號。
由於可基於提議號對提議進行排序，可通過防止兩個或多個裝置對兩個或多個不同的提議使用同一提議號來獲得效率。因此，提議號可由使用基於諸如發送提議的裝置的媒體訪問控制(MAC)地址等唯一裝置屬性的機制的裝置來選擇。可選地，提議號可在裝置之間進行分區，要求每一裝置僅從其分區中選擇提議號。用於對提議號進行分區的一種方法是向「第i個」裝置授予對系統中的裝置數與「i」同餘的提議號。
如將示出的，由於Paxos算法即使在多個裝置擔當領導者時也能運作，裝置假定領導者地位位置的機制是不重要的。然而，將不同的裝置同時認為它們是領導者的機會最小化的機制可提高系統的效率。例如，基於諸如MAC地址等唯一裝置屬性的機制可降低同時具有一個以上領導者的機會。一個這樣的機制可簡單地選擇具有最小MAC地址的正確運作的裝置作為下一領導者。另外，領導者選擇機制可防止裝置在已在預定時間內從擔當領導者的另一裝置接收消息時變成領導者。這一恆定的領導者改變可向系統的操作引入低效率。
轉向圖3b，在接收到諸如消息200等建議新提議號的消息之後，裝置11和12的每一個可用指示仍小於由消息200建議的提議號的最大提議號的消息，以及由該消息提議的裝置所投票的功能來響應。如果裝置已投票贊成了大於由領導者使用的提議號的提議號，則裝置可忽略來自領導者的消息，或如下文所解釋的，裝置可用最後一個投票信息來響應，而不管更大的提議號是什麼。在圖3b所示的示例性情況中，裝置12先前已投票贊成了提議號70，該提議號提議系統10執行由變量「y」標識的功能。由此，響應於消息200，裝置12可發送指示它最後一次投票贊成提議執行功能「y」的提議號70的消息212。類似地，裝置11先前投票贊成了提議號30，它提議系統10執行由變量「z」標識的功能。因此，消息211可將裝置11的最後一個投票信息傳送回裝置13。裝置13可能尚未接收到任何提議，並且因此，先前未投票贊成任何提議。因此，它可返回如由消息213所指示的空響應。再一次，如上所述，從裝置13發送到其自身的消息可由裝置13內部地處理，但是為說明性目的仍示出該消息。
轉向圖3c，當領導者13接收消息211-213時，領導者可確定要提議的適當的功能，使得所提議的功能等效於具有由法定人數的任一成員投票贊成的最大提議號的功能。如果沒有一個法定人數成員對任何先前的提議投票，則領導者可自由選擇它所期望提議的任何功能。因此，給定圖3b所示的消息211-213，裝置13可選擇請求投票贊成功能「y」的執行，因為該功能由裝置12投票贊成作為提議號70的一部分，它是具有領導者13所獲悉的最大提議號的提議。然而，由於圖3a到3e所示的系統10包含三個裝置，因此法定人數可少至兩個裝置。由此，僅從裝置11到13就足以使領導者13請求投票贊成提議。在這一情況下，領導者13不需要提議功能「y」，因為裝置12不是所選擇的法定人數的成員。相反，領導者13可提議功能「z」，因為該功能由裝置11投票贊成作為提議號30的一部分。由於提議號30是由法定人數中的裝置投票的最大提議號，因此領導者可選擇功能「z」來提交到投票。
由於建議提議號的消息200擔當領導者13可用於確定要選擇的適當的提議號的機制，並且使領導者能夠獲悉先前所提議的所有標號較低的提議，因此領導者13必須發送多個消息，如消息200，如果較早的消息的提議號太低，則遞增地建議較大的提議號。與要求領導者發送多個消息相反，每一裝置可用它所投票的最大標號的提議來響應，而不考慮由領導者建議的提議號是大於還是小於先前所投票贊成的提議。以這一方式，領導者13可更有效地獲悉先前的投票，並更準確地選擇用於提議功能的提議號。
轉向圖3c，示出領導者13選擇包括系統10的所有裝置的法定人數，並發送尋求對由系統10執行功能「y」進行投票的消息220。在接收到消息220之後，每一裝置可確定是否投票贊成功能「y」。只要裝置尚未響應具有大於當前對其請求投票的提議的提議號的新提議的建議，裝置可可投票贊成功能。由此，對於圖3c所示的示例，如果裝置11-13的任一個在領導者13發送如圖3c所示的消息220之前已接收並響應了對具有大於100的提議號的新提議的另一建議，則該裝置不能投票贊成由消息220對其請求投票的功能。
轉向圖3d，裝置11-13的每一個可獨立地確定它們沒有回覆具有大於100的提議號的新提議的其它建議。因此，由於它們所響應的新提議的最後一個建議不是對具有大於當前提議的提議號的提議的建議，因此裝置11和13可投票贊成該提議並分別在消息231和233中指示它們的投票。如上所述，為說明目的示出消息233，並可對裝置13內部地處理。然而，裝置12可在消息220的發送之前的某一時刻接收並響應對具有大於100的提議號的新提議的建議。因此，在接收到消息200之後，裝置12可確定它已響應了對具有大於100的提議號的新提議的建議，並且因此，不能投票贊成提議100。作為結果，如圖3d所示，裝置12用通知領導者13它已響應了對具有提議號150的提議的建議的消息232來響應。如果領導者13確定它需要裝置12的投票，則它可發送類似於消息220的另一消息，其不同之處在於提議號大於150。可選地，裝置12不需要響應消息220，並且如果裝置13需要裝置12的投票，它可嘗試對具有任意大的提議號的提議作另外的投票。如可見的，如果裝置12不向領導者13指示更大的提議號，則領導者必須猜測，並且會浪費資源來通過多個消息猜測適當大的提議號。
然而，由於裝置11和13足以構成法定人數，因此即使沒有裝置12的投票，領導者13也可確定該提議已被接受，並可用如圖3e所示的消息240請求裝置11和12的每一個執行功能「y」。儘管裝置11和13的確構成法定人數，它並不是領導者13向其提交要投票的提議的同一法定人數，該團體包括裝置12。然而，如上所述，領導者只需從法定人數接收投票，並且該法定人數不必要是向其發送請求的同一法定人數，以確定提議已被接受。上述Paxos算法確保對於其操作中的任一給定的步驟，系統10僅選擇並執行一個功能。例如，如果先前不操作的另一裝置變為可操作並重新加入系統10，則它可試圖對系統選擇並執行「y」的同一步驟提議不同於「y」的功能。如果這一裝置發送具有小於100的提議號的提議，則它可被裝置11和13忽略，因為它們已如圖3d所示地投票贊成了提議號100。另一方面，如果裝置發送具有大於100的提議號，如提議號130的提議，則裝置11和13可返回一指示它們已投票贊成提議號100中的功能「y」的消息。如圖3d中所示的，由於裝置12尚未投票，因此它可用指示它已投票贊成提議號30中的功能「z」的消息212來響應。
新裝置然後可選擇法定人數中的最大提議，該法定人數按定義可包括裝置11-13的至少部分，並且新裝置可提交該提議中所提議的功能用於投票。由此，對於提議130，新裝置可提交功能「y」用於投票。每一裝置然後可遵從上述算法來對提議130進行投票。可選擇提議130，這不會改變對特定步驟執行功能「y」的先前決策，或者，提議130會失敗，因為有太多裝置同時允諾投票贊成另一提議。然而，如所見的，一旦提議被通過，所有其它提議將提議同一功能，並且按照定義，所有的裝置只能投票贊成該同一功能。以這一方式，Paxos算法確保系統10的每一裝置對給定的步驟執行同一功能。
如上所述，Paxos算法的應用可使分布式計算系統對給定的步驟選擇一個功能來執行。通過重複上述步驟，分布式計算系統可對要作為一系列步驟執行的一系列功能達成一致，並由此，可形成一連續的作業系統。以這一方式，分布式系統可從一個或多個客戶機接收請求、可執行那些請求、並可向客戶機返回結果。
轉向圖4a，系統10可以是已經可操作若干步驟。例如，在圖4a所示的示例性系統10中，最近執行的步驟可以是步驟24，並且步驟25可以是當前步驟。然而，先前擔當領導者的裝置可能會發生故障，或僅僅未接收到任何客戶機請求。如圖所示，客戶機20可使用消息300向裝置13發送執行功能的請求，由圖4a中的變量「x」表示。依照諸如上述的任意數量的機制，裝置13可確定它應當變為領導者。由此，裝置13可發送建議對下一提議使用提議號100，並包括對其作出提議的步驟的消息301。在圖4a所示的示例性分布式計算系統10中，裝置13不知道步驟23和24已被確定並由其它裝置11和12執行。由此，消息301指示它對步驟23建議提議號100。
為加速執行多個步驟的系統中的算法的操作，諸如消息301等消息可被理解成對大於或等於步驟23的所有步驟建議提議號100。以這一方式，領導者13不需要連續地發送諸如消息301等消息，直到它獲悉已被決定的每一步驟。相反，裝置13可通過僅一個消息往返來獲悉已執行的步驟，這在下文示出。
轉向圖4b，示出了來自分布式系統10的裝置11-13的消息311-313。例如，裝置11記錄對步驟23執行了功能「y」，並對步驟24執行了功能「z」。由此，在接收消息301之後，裝置11可用指示它儲存為對大於或等於23的所有步驟-在這一情況下為步驟23和24-執行的功能的消息311來響應。另外，裝置11可提供具有最大提議號的提議的指示，對大於或等於25的步驟投票贊成那些提議。由此，在圖4b所示的示例中，消息311也可指示裝置11未對大於25的步驟投票贊成任何提議，並且它投票贊成了提議號160-對步驟25提議功能「b」。為減少在系統10中發送的消息數，如果裝置不知道對給定步驟所執行的功能，它們只需用其最高提議號來響應。由此，由於裝置11知曉對步驟23和24執行了功能，但是未對步驟25執行，因此它用對步驟23和24所執行的功能以及對步驟25所投票贊成的最高提議號來響應。
如上所述，裝置13既可擔當領導者又可擔當投票裝置。由此，裝置13可向其自身發送消息，如消息301，並可用諸如消息3113等消息來向其自身響應。這些消息在圖中僅為說明性目的示出，並且它們可能對裝置13內部地發送。此外，由於裝置13可檢查具有它所知道已對其執行了功能的最大步驟號的步驟是什麼，並且它可檢查對高於裝置13所投票贊成的所有步驟的提議的最大提議號是什麼，因此消息313除空指示符之外應當幾乎不包含任何信息。
狀態機的當前狀態不僅可取決於所執行的功能，還可取決於執行這些功能的順序。因此，如果裝置不知道對給定的步驟執行了哪一功能，會有以下情況裝置不應當執行超出該步驟之外的任何功能，或者它會不按順序地執行功能，並且其狀態會不同於分布式計算系統的狀態。例如，某些功能，如無條件地指定新狀態的功能，與裝置的當前狀態無關。即使對於具有低於當前步驟的步驟號的步驟的功能尚未被執行，這類功能也可被執行。類似地，對其可在不知道所有先前步驟的情況下計算輸出的功能，如寫入資料庫，也可不按順序地部分執行，以生成發送給客戶機的輸出。然而，一般而言，功能不應當在執行了所有先前的功能之前被執行。因此，裝置可以總是試圖獲悉對裝置所錯過的步驟執行了哪些功能。當裝置13發送消息301時，如圖4a所示，它是一種隱含的語句，裝置13相信步驟23是下一個步驟，並且它已通過步驟22執行了所達成一致的功能。因此，錯過低於步驟23的步驟的功能的裝置知道裝置13已經通過步驟22執行了所有的功能，並且它可向裝置13請求該功能。
轉向圖4b，裝置12不知道對步驟12執行了哪些功能。結果，裝置12可能無法執行自從步驟11以來的任何功能，即使它可能知道對步驟13-23所執行的功能。由此，在消息312中，裝置12可向領導者13請求步驟12的功能。另外，裝置12可指示它尚未對標號高於步驟23的步驟投票贊成任何提議。
如果裝置錯過了太多步驟，則僅向裝置通知當前狀態，而非發送它所錯過的所有步驟的所有功能將會更有效。確保裝置不會錯過太多步驟的一種機制是使每一裝置，或裝置的集合能夠周期性地拍攝狀態的各種部分或整個狀態的快照。因此，另一裝置的狀態能夠通過發送其適當的快照以及自從最後一次快照以來所執行的功能來更新。另外，通過使用狀態的各個部分的校驗和，另一裝置的狀態可通過僅向其它裝置發送不同於其當前副本的狀態部分來更新。
作為接收消息311到313的結果，領導者13可執行它先前不知道的步驟23和24、試圖確定向步驟25提議的適當功能、並試圖更新同樣尚未執行到步驟25的所有步驟的其它裝置。最初，領導者13在消息301中建議提議號100，但是裝置11用指示它已為步驟25投票贊成具有大於100的提議號的提議的消息311來響應。因此，領導者13可選擇大於領導者所知道的最大提議號的提議號，並發送另一建議消息，如圖4c所示的消息320。可選地，裝置11可以簡單地忽略消息301中對提議號100的建議，因為該提議號小於裝置11已經投票贊成的提議的提議號。在這一情況下，領導者可通過增大提議號來重試，試圖考慮忽略最初建議的裝置。如所見的，如果裝置忽略對其提議號小於裝置已投票贊成的提議的提議號的提議的建議，則領導者被強迫執行多次重試，每次增大所建議的提議號。這些多個消息將是低效率的。因此，較佳的是裝置響應對新提議號的所有建議，即使該提議號小於裝置已投票贊成的提議的提議號，因為領導者那時可以較精確地確定要建議的適當的提議號，並可避免多個消息。
轉向圖4c，領導者13可建議較大的提議號，如消息320中所示的提議號200，試圖建議大於領導者13所獲悉裝置先前已投票贊成的任何提議的提議號的提議號。另外，領導者13也可向尚未執行步驟25以前的所有選擇的功能的任何裝置提供關於先前執行的功能的信息。因此，如圖所示，領導者13也可發送消息321，向裝置12指示對步驟12執行由變量「e」表示的功能，並且對步驟23和24分別執行由變量「y」和「z」表示的功能。
然後，在圖4d中，裝置11-13可以類似於圖4b中所示的方式來響應，例外的是裝置11-13不需要向裝置13通知對步驟23和24所執行的步驟，因為裝置13已獲悉了這些步驟，並且已發送了涉及步驟25的消息320和321。此外，消息331-333可包含額外的信息，如裝置已投票贊成的另外的提議。例如，裝置12在發送消息312和332之間的某一時刻可投票贊成具有提議號190的提議。因此，消息312可指示裝置12先前未對步驟25投票贊成任何提議，但是消息332可指示裝置12對步驟25已投票贊成提議190，儘管它仍未對大於25的任何步驟投票贊成任何提議。然而，由於每一提議號都小於領導者13在消息320中發送的所建議的提議號，因此領導者可繼續提議具有消息320中指定的提議號200的功能。
轉向圖4e，領導者13現在具有足夠的信息以選擇一個提議來作為提議號200提交，如由消息340所示的，它請求裝置11-13投票贊成提議200，提議系統對步驟25執行功能「b」。如上所述，由於裝置11和12都是法定人數的成員，它們先前都投票贊成了提議執行功能「b」的提議，並且沒有法定人數的其它成員投票贊成了更大標號的提議，因此領導者13可對提議號200提議功能「b」，儘管客戶機20在消息300中請求執行功能「x」。以這一方式，Paxos算法確保先前所提議但未完成的功能一如由於一個或多個裝置或其通信的故障而未完成一可以按正確的順序執行。
圖4f示出了對步驟25，裝置11-13分別用消息351-353投票贊成提議功能「b」的提議200。如上所述，只要裝置未在接收消息320和340之間允諾投票贊成具有更大提議號的不同提議，它就可投票贊成提議。一旦領導者13接收消息351-353，它可如圖4g所示地發送消息360，指令裝置11和12對步驟25執行功能「b」。領導者13也可執行該功能本身，因為它知道該功能由一法定人數選擇。
然而，在圖4g所示的時刻，客戶機20在消息300中請求的功能尚未被系統10執行。為令系統10執行客戶機的請求，領導者13可執行由上文的圖3a-e和圖4a-g所示的完整Paxos算法的縮略版本。
概念上，上文描述的Paxos算法可被劃分成兩個通用階段。第一階段包括領導者獲悉由法定人數中的裝置投票贊成的先前的提議。第一階段可包含由領導的提議號建議和法定人數的其它成員的響應的一次迭代，如圖3a和3b所示的，或者提議號建議和響應的多次迭代，如圖4a-d所示的。第二階段包括領導者提交用於投票的提議的功能接收投票，並且如果該提議由足夠數量的裝置投票贊成，則指令裝置執行所達成一致的功能。第二階段的示例由圖3c-e和4e-g示出。
一旦領導者獲悉了其它提議，並找出對所有當前和未來步驟都安全的提議號，它不需要請求進一步的消息，除非它發生故障，或另一裝置試圖成為領導者。因此，Paxos算法的第一階段可較不頻繁地執行，而第二階段可被重複地執行，每次增大步驟號，允許分布式計算系統達成一致並執行一系列功能和維護活動的運行狀態。
轉向圖5a，示出了圖4a-g的示例性分布式計算系統10在上文詳細描述的步驟25之後執行另外的步驟26。作為如圖4a-d所示並在上文詳細描述的Paxos算法的第一階段的結果，領導者13已知曉了沒有一個裝置11-13投票贊成了步驟25以上的任何提議，並且因此，提議號200對高於步驟25的所有步驟都是安全的。因此，如圖5a所示，對於步驟26，領導者可啟動Paxos算法的第二階段，而無需再次執行第一階段，並可發送消息400，請求對由客戶機在消息300中所請求的功能「x」的執行進行投票。裝置11-13的每一個然後可用投票作出響應，如圖5b用411-413所示的。由於法定人數中的每一裝置已投票贊成了功能的執行，因此領導者13可用圖5c中所示的消息420發信號通知裝置11和12對步驟26執行功能「x」。另外，由於領導者13知道投票已成功，它可執行功能「x」並向客戶機發送該功能的執行結果的消息421，或作為消息422向其它感興趣的計算裝置，如裝置30和31發送。消息421和422可與消息420並發地發送，或甚至在消息420之前或之後發送。
如所見的，一旦領導者已建立並獲悉了法定人數中的裝置對所有即將到來的步驟號所投票贊成的各種最高標號的提議，領導者可請求提議來投票，而無需循環通過Paxos算法的第一階段。儘管圖5a所示的消息被描述為在圖4g的消息360的發送之後出現，然而領導者13在對隨後步驟發送另一提議之前不需要等候裝置投票贊成一個提議。因此，如圖4e所示，在發送消息340之後，領導者13可如圖5a所示地發送消息400，並可以這一方式繼續提議一系列功能，對大於步驟26的步驟使用提議號200。通過以這一異步的方式操作，整個分布式計算系統無需因等候來獲悉對先前步驟的投票而被降低速度。
萬一另一裝置，如先前的非運作裝置，試圖成為領導者，它不會導致系統不正確地執行，但是只能成功地導致算法的第一步驟被重複。例如，如果另一裝置試圖成為領導者，它必須建議某些裝置將會響應的提議號。響應了由第二領導者提供的提議號之後，在第一領導者請求投票時，裝置然後向第一領導者通知最高標號的提議，或者裝置可忽略第一領導者對其提議進行投票的請求。當該提議由於沒有足夠數量的裝置投票贊成它而失敗時，第一領導者將通過最初再次執行第一階段並選擇可向裝置建議的它所認為的足夠大的提議號，來試圖再次通過該提議。以這一方式，第二領導者將僅延遲該系統，但是它不會導致分布式計算系統的一部分的不正確操作。
實現上述Paxos算法的步驟的裝置可維護儲存算法中使用的信息的變量。例如，對於對其裝置不知道選擇了哪一功能的每一步驟，裝置可儲存它們所響應的具有最大提議號的提議的提議號、它們所投票贊成的具有最大提議號的提議的提議號、它們所投票的具有最大提議號的提議所提議的值，並且如果該裝置是領導者，它可另外儲存它所發出的最後一個提議的提議號。另外，裝置可記錄對它們具有信息的所有步驟選擇了哪些功能。可選地，如上所述，裝置可儲存給定時刻的其狀態的快照，以及僅自從那一時刻以來所執行的功能。這些變量可儲存在易失存儲130或非易失存儲中，如圖2所示的硬碟141、軟盤152或光碟156。
Paxos算法的額外的信息可在Leslie Lamport的名為「The Part-time Parliament」的論文中找到，發表在ACM Transactions on Computer Systems上，16卷，2號，133-169頁，1998年5月，該論文通過整體引用結合於此。
簡化的Paxos算法如從上文的標準Paxos算法的詳細描述可見到的，在客戶機向實現Paxos算法的分布式計算系統發送請求和從系統發送對客戶機請求的響應之間會引入一系列的消息延遲。即使接收客戶機請求的裝置已經是易完成標準Paxos算法的第一階段的領導者裝置，仍會引入消息延遲。例如，轉向圖6a，示出了前面的附圖的分布式計算系統10，它具有前一領導者13，它從請求系統執行由變量「w」表示的功能的客戶機20接收客戶機請求500。由於領導者13已執行了Paxos算法的第一階段，並且沒有其它裝置試圖請求投票，因此領導者只需執行Paxos算法的第二階段以令系統10執行客戶機請求500。因此，在接收客戶機請求500之後，領導者13可發送請求對系統的下一步驟(在當前示例中為步驟27)執行作為提議號200的功能「w」的投票。消息501的發送可引入一個消息延遲。裝置11-13的每一個然後可用投票響應，如在圖6b中用消息511-513所示的。消息511-513的發送可引入另一消息延遲。由於法定人數中的每一裝置投票贊成該功能的執行，因此領導者13可用如圖6c所示的消息520發信號通知裝置11和12對步驟27執行功能「w」。另外，由於領導者13知道該投票已成功，它可執行功能「w」，並可向客戶機發送該功能的執行結果，作為消息521，或者向其它感興趣的計算裝置，如裝置30和31發送，作為消息522。因此，標準Paxos算法可在接收客戶機請求消息500和向客戶機發送回復消息521之間引入至少兩個消息延遲。
在本發明的一個實施例中，通過修改標準Paxos算法的第二階段，可避免至少一個消息延遲。在包括三個裝置的分布式計算系統中，如系統10，任意兩個裝置可形成多數。由於任意兩個多數可具有公用的至少一個裝置，因此為執行Paxos算法的目的，三個裝置系統中的任意兩個裝置也可以是法定人數。由此，如果任意兩個裝置對執行提議的功能達成一致，則可由系統選擇並執行所提議的功能。領導者可以是這兩個裝置法定人數的一個裝置。因此，如果其它兩個裝置中的任一個投票贊成提議的功能的執行，則法定人數選擇該功能。
如果領導者在發送對特定功能的投票請求的同時一起發送領導者對該功能的投票的指示，則可避免一個消息延遲。當另一裝置接收這一消息時，它可自己形成對提議的功能的執行投票的法定人數，而無需任何其它消息。因此，如果裝置確定它應當投票贊成所提議的功能，並且它已接收了領導者對同一提議的功能的投票，則它也可確定包括它本身和領導者的法定人數已投票贊成了該功能的執行。由於法定人數已投票贊成了該功能的執行，因此裝置可在不接收任何其它消息的情況下安全地執行該功能。一旦裝置執行了該功能，它可向客戶機或任何其它感興趣的裝置發送回結果，由此與標準Paxos算法相比消除了一個消息延遲。
轉向圖7a，參考前面的附圖的系統10示出了本發明的一個實施例的操作。如圖6a所示，領導者13可接收客戶機對執行由變量「v」表示的功能的請求，如圖7a中的消息600。領導者13隨後可向裝置11和12發送消息601，它不僅包括對提議的功能的投票請求，還包括領導者贊成所提議的功能的投票。由此，圖7a中的消息601包含上述圖6a的領導者消息501中不存在的額外信息。具體地，消息601也包含領導者在上述圖6b中的消息513之前不發送的信息。
轉向圖7b，由於裝置11和12知曉裝置13已投票贊成了所提議的功能，並且由於任意兩個裝置構成了系統10中的法定人數，因此如果投票贊成，則裝置11和12可獨立地執行所提議的功能。由此，如圖7b所示，裝置11和12可決定投票贊成所提議的功能。由於裝置11和12的每一個都知曉其自己的投票，並且它們的每一個也知曉裝置13贊成所提議的功能的投票，因此裝置11和12獨立地知道法定人數已投票贊成了所提議的功能，因此，執行該功能是安全的。裝置11和12因此可執行該功能，並用圖7b所示的消息611和612向客戶機20或任意其它計算裝置直接提供功能「v」的執行結果。因此，如可以見到的，通過連同提議一起發送投票，客戶機請求600和系統響應之間的唯一消息延遲，以消息611或612的形式，為發送消息601中的延遲。
在本發明所考慮的另一實施例中，領導者13選擇系統10中的唯一的一個其它裝置來組成法定人數，並通告請求的功能的執行結果。因此，轉向圖8a，示出了圖7a的一個替換方案。具體地，如圖8a所示，當領導者13接收客戶機請求700時，它可向裝置11僅發送消息701，包括對所請求的功能的投票請求，以及領導者對該功能的投票的指示。如上所述，如果裝置11決定投票贊成該功能，則它知道包括它本身和領導者的法定人數已投票贊成了該功能，並且它可安全地執行該功能，並向客戶機20和其它感興趣的裝置提供結果。由此，如作為圖7b的替換方案的圖8b所示，裝置11不僅可向客戶機20和其它感興趣的裝置30和31通知請求的功能的執行結果，也可向裝置12通知功能的執行結果。然而，由於裝置12可試圖維護系統狀態的當前副本，因此裝置11也可提供所選擇功能以及它是對哪一步驟所選擇的指示。由此，儘管發送到客戶機20和其它感興趣的裝置30和31的消息711隻需包含所選擇的功能的執行結果，然而裝置12可接收指示對步驟28選擇功能「v」，並提供功能「v」的執行結果的消息721。
在圖7a和b以及8a和b所示的任一實施例中，執行所請求的功能的裝置可向領導者13發送功能「v」被選擇的事實，並可提供執行功能「v」的結果，以令領導者13能夠維護系統狀態的當前副本。可選地，領導者13不需要維護系統的狀態，從而消除了執行功能的裝置向領導者發送更多消息的需要。
不論領導者是否維護系統的狀態，只要維護了系統狀態的兩個副本，系統10可容許故障。例如，如果領導者13不維護系統狀態的副本，並且裝置11和12的確維護副本，則如果裝置11或12的任一個發生故障，系統可繼續僅用領導者13和兩個裝置11或12中可操作的一個來操作。所發送的消息可類似於圖8a和8b中所示出的消息，其中，領導者僅向一個裝置發送消息。
為將在系統10的裝置之間所發送的消息的數量最小化，本發明的一個實施例考慮高速緩存結果消息，並以加速的方式將它們作為批處理消息發送給領導者或不需要知道功能的執行結果的其它裝置。由此，如果領導者的確維護系統狀態的一個備份副本，諸如圖8b中所示的消息711等結果消息可被高速緩存在發送裝置上，並且在預定的時間間隔之後，或可選地在高速緩存了足夠數量的消息之後，可將結果消息作為包含多個結果消息的批處理消息發送給領導者。這一技術可類似地用於對其它裝置，如裝置30和31的消息。通過高速緩存結果消息並在預定時間間隔之後將它們作為批處理消息發送，可減少消息的數量，並進而減少發送裝置的網絡接口上的網絡擁塞和負載。
由於領導者可能不接收請求的功能的執行結果，因此可使用其它機制來核實諸如裝置11和12等其它裝置實際接收的包含由領導者發送的投票請求和領導者投票的消息。在本發明所考慮的一個實施例中，裝置11和12可向領導者13發送小確認消息，以確認它們接收到了領導者消息。此外，確認消息也可被高速緩存並在預定時間間隔之後以上述方式作為批處理消息發送。在本發明考慮的另一實施例中，可使用一種可靠的底層傳輸機制。如本領域的技術人員已知的，可靠傳輸機制獨立地核實消息的發送，並且如有必要，獨立地高速緩存和重新發送消息。因此，可靠底層傳輸機制的使用消除了作為一致同意算法的一部分的明確消息驗證的需要。
上文詳細描述的更有效的Paxos算法保留了它同樣在上文詳細描述的標準Paxos算法的容錯屬性。具體地，附圖中所示的三個裝置的系統10可容許一個故障。例如，如果裝置12發生故障，則系統能夠以上文參考圖8a和8b所描述的方式繼續操作，因為任意兩個裝置，即本示例中的領導者和裝置11可構成法定人數，並可選擇功能來執行。
如果裝置13發生故障，或裝置11或12之一試圖成為領導者並向系統10提交提議，則必須執行上文詳細描述的標準Paxos算法的第一階段，以使領導者獲悉先前的提議並確定適當的提議號。然而，如上所述，在一般所預期的操作條件下，Paxos算法的第一階段比Paxos算法的第二階段更不頻繁地執行。因此，通過消除Paxos算法的第二階段的消息延遲，在一般所預期的操作條件下，上述算法可導致對客戶機的更快響應，即使標準Paxos算法的第一階段仍會被偶然執行以向領導者提供信息。
用廉價裝置的簡化Paxos算法如上所述，Paxos算法可用於使用包括任何類型計算裝置的系統提供容錯的分布式計算。僅作為示例，分布式系統可包括在全球範圍內提供冗餘度的高速專用伺服器計算裝置，或者系統可排他地包括來自向收入有限的組織或研究所提供廉價冗餘處理和存儲的個人計算裝置的未使用資源。然而，如果為選擇的要執行的功能所需要的計算裝置的法定人數是由計算裝置的法定人數本身選擇的，則可進一步節省計算資源。具體地，上述算法可由其中一個裝置可具有非常低的處理能力或存儲能力的分布式計算系統來實現。以這一方式，可主要向分布式計算系統的其它裝置分配計算預算，使得能夠購買更強大的計算裝置，而只需向僅具有最小處理能力或存儲能力的那一個裝置分配最小的貨幣資源。
轉向圖9a，示出了具有兩個裝置11和13以及以個人數字助理(PDA)的形式示出的廉價計算裝置14的分布式計算系統19。儘管示出裝置14為PDA，然而本領域的技術人員可以理解，它可以是任一類型的計算裝置，正如裝置11和13可以是任一類型的計算裝置一樣。然而，貨幣資源的最有效使用可通過購買更強大的計算裝置11和13，併購買較不強大的計算裝置12，包括諸如PDA、可編程計算器、或甚至是數字腕錶等裝置來實現。
在提交投票提議之前，領導者13可試圖選擇可操作的法定人數，它可以投票，並且如果被選擇，可執行所提議的功能。可操作的法定人數的選擇可以類似於上文詳細描述的提議功能的選擇的方式來發生。由於裝置13已將其自身建立為領導者裝置，如上文所詳細描述的，它可繼續提議可操作的法定人數。由此，如圖9a所示的，領導者13可發送對特定可操作法定人數的投票請求，以及該領導者對所提議的可操作法定人數的投票。在圖9a所示的具體示例中，領導者13提議包括裝置11和13的可操作法定人數，並向裝置11和14發送該提議以及其投票。
轉向9b，示出裝置11和14的每一個同意所提議的可操作法定人數，並向系統19的其它裝置通知它們的同意。如上所述，本發明考慮的另一實施例允許裝置13僅發送一個消息800，如僅向裝置14發送。在這一情況下，裝置14可向裝置11和13發送消息814，向它們通知可操作法定人數的選擇。
一旦選擇了可操作法定人數，它可用於投票贊成並執行提議的功能。因此，轉向圖10a，領導者13可從客戶機20接收執行由變量「u」表示的功能的請求900。如上所述，領導者13可在消息901中發送執行所請求的功能的提議以及領導者對該提議的投票。然而，由於了選擇可操作法定人數為裝置11和13，裝置13隻需向裝置11發送消息901。
轉向圖10b，如果裝置11確定它應當投票贊成包含在消息901中的提議，它可繼續執行功能「u」，因為裝置11知道它和裝置13都投票贊成了功能「u」的執行。由此，如圖10b所示的，裝置11可在不等候額外消息的情況下執行功能「u」並在消息911中向客戶機20發送結果。如上所述，領導者也可維護系統狀態的副本，它可從裝置11接收消息921，該消息不僅提供功能「u」的執行的結果，也提供對步驟30選擇功能「u」的指示。可選地，裝置11可僅發送功能「u」的選擇的指示，並允許裝置13在系統狀態的其自己的副本上執行功能「u」。
如可見到的，裝置11和13可執行多數計算工作，並可維護系統狀態，可能需要大量的存儲資源。另一方面，裝置14介入到那個程度，即它作為選擇裝置11和13的可操作法定人數法定人數的一部分。由此，如上所述，裝置14可以是廉價裝置。
分布式計算系統19仍可容忍一個裝置的故障，正如先前所示出並描述的系統10那樣。例如，並轉向圖11a，示出裝置11發生故障。裝置11的故障可由裝置13通過各種方法的任一種來檢測，包括查驗、超時等等。由於裝置11不再正確地運作，因此裝置13可提議將可操作法定人數改變成僅包括其本身的可操作法定人數。儘管可操作法定人數可以少於多數，然而以這一方式修改可操作法定人數的決策可用系統19的傳統法定人數來做出，後者可以是多數。由此，裝置13向裝置14發送包括改變可操作法定人數的提議以及對該提議的其自己的投票的消息1000。
由於裝置14可以是具有有限處理或存儲能力的廉價裝置，因此本發明的一個實施例允許裝置14對它所接收的每一提議進行投票，只要裝置14先前未響應具有更高提議號的另一消息，如上文所詳細描述的。因此，裝置14不需要儲存大量的信息，也不需要執行大量的處理。轉向圖11b，裝置14可用指示它投票贊成包括裝置13的可操作法定人數的消息1014對裝置13響應。然後，裝置13本身可擔當分布式計算系統19的法定人數。
轉向圖12，客戶機20可向領導者13發送消息1100，以使系統19執行由變量「t」表示的功能。然而，如圖11a和11b所示的，新的可操作法定人數僅包含裝置13。因此，在接收到客戶機請求1100之後，裝置13可確定是否執行該請求，並且如果它執行該請求，它可將結果以返回消息1101的形式發送回客戶機20。由於圖12所示的可操作法定人數僅包括裝置13，裝置13不需要向任何其它裝置提議客戶機的請求1100，並可獨立決定是否執行所請求的功能。類似地，如果裝置13決定執行所請求的功能，它可完成該執行，並將結果發送回客戶機20，再一次，不需要來自任何其它裝置的同意。
然而，如本領域的技術人員所理解的，允許分布式計算系統19僅使用一個裝置來實現狀態機的缺點是，如果該裝置發生故障，則沒有具有系統狀態的冗餘副本的其它裝置。轉向圖13a，示出裝置13發生故障，而示出裝置11被修復。由此，當裝置11接收客戶機請求1200時，它可試圖改變可操作法定人數來僅包括裝置11。由於裝置11不是當前的領導者裝置，它可通過對步驟31發送提議消息1201、提議提議號300來試圖成為領導者裝置。如上文詳細解釋的，裝置11可選擇大於它所知道的最大的先前的提議號的提議號。由於裝置11知道對步驟30使用提議號200，如圖10a中的消息901所示的，裝置11在試圖成為領導者時可選擇更高的提議號。類似地，由於裝置11知道對步驟30執行功能，如由圖10b中的消息911所示的，它可試圖對步驟31提議功能。
然而，裝置14已投了步驟31的票，如由圖11b中的消息1014所示的。因此，以上文詳細描述的方式，裝置14可通知裝置11其先前的投票。轉向圖13b，示出裝置14向裝置11發送最後一個投票消息1214，通知它裝置14先前已投票贊成了將可操作法定人數設為裝置13的步驟31的提議。裝置11然後可確定正確的可操作法定人數可包括裝置13，並且它可試圖對大於31的步驟提議包括裝置13的可操作法定人數。可選地，裝置11可在提議任何其它功能之前僅等候裝置13再次成為可操作的。在任一情況下，裝置11在它知道當它獨立構成法定人數時裝置13執行了哪一功能之前不能執行功能。因此，系統19在裝置13被修復或重啟之前不能執行進一步的行動。
在本發明考慮的一個替換實施例中，可操作法定人數的選擇可在對功能的每一投票之前發生。以這一方式，僅當前運作的裝置可成為可操作法定人數的一部分。然而，如本領域的技術人員已知的，如果裝置不經常發生故障，這一實施例是低效率的。
如可以見到的，通過減少施加在諸如裝置14等裝置上的要求，可選擇分布式計算系統的一個裝置為具有有限計算能力和存儲容量的廉價裝置。然而，整個分布式計算系統可以容錯方式繼續運作，使用廉價裝置的唯一缺點是，如果由於故障，可操作法定人數僅由一個裝置實現，並且然後該裝置在其它裝置被修復或重啟之前發生故障，則系統被強迫等待，直到最後實現該系統的裝置被修復，即使在該時刻之前存在可操作裝置的法定人數。
鑑於可應用本發明的原理的許多可能的實施例，應當認識到，本發明參考附圖所描述的實施例僅意味著說明性的，並且不應當作為對本發明的範圍的局限。例如，本領域的技術人員將認識到，以軟體形式示出的所示的實施例的某些元件可以硬體實現，並且反之亦然，或者可在不脫離本發明的精神的情況下在排列和細節上修改所示的實施例。因此，此處所描述的本發明考慮所有這樣的實施例都落入所付權利要求書及其等效技術方案的範圍之內。
權利要求
1.一種在分布式計算系統中選擇一值的方法，其特徵在於，所述方法包括發送提議的值、對所提議的值的投票、第一提議標識符和第一步驟標識符，其中，對所提議的值的所述投票向第一接收裝置提供了足夠的信息，以便基於對所提議的值的所述投票及其自己的投票來確定是否所述分布式計算系統的第一法定人數已經在由所述第一步驟標識符標識的第一系統步驟中選擇了所提議的值。
2.如權利要求1所述的方法，其特徵在於，它還包括發送對一可操作法定人數的提議、對所述可操作法定人數的提議的投票、第二提議標識符和第二步驟標識符，其中，對所述可操作法定人數的提議的所述投票向第二接收裝置提供足夠的信息，以便基於對所述可操作法定人數的提議的所述投票以及其自己的投票確定是否所述分布式系統的第二法定人數已經在由所述第二步驟標識符標識的第二系統步驟中選擇了對所述可操作法定人數的提議；以及接收對所述可操作法定人數的提議的選擇的指示。
3.如權利要求2所述的方法，其特徵在於，所述分布式計算系統的第二法定人數包括第二發送裝置和第二接收裝置，其中，所述第二發送裝置發送對所述可操作法定人數的提議、對所述可操作法定人數的提議的投票、第二提議標識符和第二步驟標識符，並且其中，所述第二接收裝置是廉價計算裝置。
4.一種用於在分布式計算系統中選擇一值的方法，其特徵在於，所述方法包括接收一提議的值、對所提議的值的投票、第一提議標識符和第一步驟標識符，其中，對所提議的值的所述投票提供足夠的信息，以確定所述分布式計算系統的第一法定人數是否已經在由所述第一步驟標識符標識的第一系統步驟中選擇了所提議的值。
5.如權利要求4所述的方法，其特徵在於，它還包括如果所述第一提議標識符大於或等於先前響應過的提議標識符時，選擇所提議的值，並在不等候額外消息的情況下向原先提議所提議的值的客戶機裝置發送所提議的值的選擇。
6.如權利要求4所述的方法，其特徵在於，它還包括接收對一可操作法定人數的提議、對所述可操作法定人數的提議的投票、第二提議標識符和第二步驟標識符，其中，對所述可操作法定人數的提議的投票提供足夠的信息，以確定所述分布式系統的第二法定人數是否已經在由所述第二步驟標識符標識的第二系統步驟中選擇了對所述可操作法定人數的提議；如果所述第二提議標識符大於或等於先前響應的提議標識符，對所述可操作法定人數選擇所述提議；以及發送對所述可操作法定人數的所述提議的選擇的指示。
7.如權利要求6所述的方法，其特徵在於，所述分布式計算系統的第二法定人數包括第二發送裝置和第二接收裝置，其中，所述第二發送裝置發送對所述可操作法定人數的提議、對所述可操作法定人數的提議的投票、所述第二提議標識符和所述第二步驟標識符，並且其中，所述第二接收裝置接收對所述可操作法定人數的提議、對所述可操作法定人數的提議的投票、所述第二提議標識符和所述第二步驟標識符，並且其中，所述第二接收裝置是廉價計算裝置。
8.一種具有用於在分布式計算系統中選擇一值的計算機可執行指令的計算機可讀媒質，其特徵在於，所述計算機可執行指令執行以下步驟發送一提議的值、對所提議的值的投票、第一提議標識符和第一步驟標識符，其中，對所提議的值的投票向第一接收裝置提供了足夠的信息，以便基於對所提議的值的投票及其自己的投票確定是否所述分布式計算系統的第一法定人數已經在由所述第一步驟標識符標識的第一系統步驟中選擇了所提議的值。
9.如權利要求8所述的計算機可讀媒質，其特徵在於，所述分布式計算系統的第一法定人數包括第一發送裝置和第一接收裝置，其中，所述第一發送裝置發送所提議的值、對所提議的值的投票、所述第一提議標識符和所述第一步驟標識符。
10.如權利要求8所述的計算機可讀媒質，其特徵在於，所提議的值是要由所述分布式計算系統執行的提議的功能。
11.如權利要求10所述的計算機可讀媒質，其特徵在於，它還具有執行以下步驟的計算機可執行指令從所述第一接收裝置接收由所述第一裝置執行所提議的功能的結果。
12.如權利要求8所述的計算機可讀媒質，其特徵在於，它還具有執行以下步驟的計算機可執行指令向所述分布式系統中的第二法定人數裝置發送對所述第一系統步驟的建議的下一提議標識符；以及從所述分布式系統中的第二法定人數裝置中的每一裝置接收建議的下一提議標識符響應，其中，如果所述第二法定人數裝置中的每一裝置先前未投票贊成所述第一系統步驟，則所建議的下一提議標識符響應為空，並且其中，如果所述第二法定人數裝置中的每一裝置先前已投票贊成了所述第一系統步驟，則所建議的下一提議標識符響應包括對應於所述第一系統步驟的先前投票贊成的值和先前投票贊成的提議標識符的指示。
13.如權利要求12所述的計算機可讀媒質，其特徵在於，它還具有執行以下步驟的計算機可執行指令選擇一大於先前投票贊成的提議標識符的任一個的標識符作為第一提議標識符；以及選擇先前所投票贊成的值之一作為所提議的值。
14.如權利要求8所述的計算機可讀媒質，其特徵在於，它還具有執行以下步驟的計算機可執行指令發送對一可操作法定人數的提議、對所述可操作法定人數的提議的投票、第二提議標識符和第二步驟標識符，其中，對所述可操作法定人數的提議的投票為第二接收裝置提供足夠的信息，以便基於對所述可操作法定人數的提議的投票及其自己的投票確定是否所述分布式系統的第二法定人數已經在由所述第二步驟標識符標識的第二系統步驟中選擇了對所述可操作法定人數的提議；以及接收對所述可操作法定人數的提議的選擇的指示。
15.如權利要求14所述的計算機可讀媒質，其特徵在於，所述分布式計算系統的第二法定人數包括第二發送裝置和所述第二接收裝置，其中，所述第二發送裝置發送對所述可操作法定人數的提議、對所述可操作法定人數的提議的投票、所述第二提議標識符和所述第二步驟標識符，並且其中，所述第二接收裝置是廉價計算裝置。
16.如權利要求14所述的計算機可讀媒質，其特徵在於，所述可操作法定人數包括所述分布式計算系統的第一法定人數，並且其中，所述第二系統步驟在所述第一系統步驟之前。
17.一種具有用於在分布式計算系統中選擇一值的計算機可執行指令的計算機可讀媒質，其特徵在於，所述計算機可執行指令執行以下步驟接收一提議的值、對所提議的值的投票、第一提議標識符和第一步驟標識符，其中，對所提議的值的投票提供足夠的信息，以確定所述分布式計算系統的第一法定人數是否已經在由所述第一步驟標識符標識的第一系統步驟中選擇了所提議的值。
18.如權利要求17所述的計算機可讀媒質，其特徵在於，所述分布式計算系統的第一法定人數包括第一發送裝置和第一接收裝置，其中，所述第一發送裝置發送所提議的值、對所提議的值的投票、所述第一提議標識符和所述第一步驟標識符，並且所述第一接收裝置接收所提議的值、對所提議的值的投票、所述第一提議標識符和所述第一步驟標識符。
19.如權利要求17所述的計算機可讀媒質，其特徵在於，它還具有執行以下步驟的計算機可執行指令如果所述第一提議標識符大於或等於先前響應的提議標識符，則選擇所提議的值並發送對所提議的值的選擇。
20.如權利要求17所述的計算機可讀媒質，其特徵在於，所提議的值是要由所述分布式計算系統執行的提議的功能。
21.如權利要求20所述的計算機可讀媒質，其特徵在於，它還具有執行以下步驟的計算機可執行指令執行所提議的功能，並發送對所提議的功能的執行結果。
22.如權利要求21所述的計算機可讀媒質，其特徵在於，它還具有執行以下步驟的計算機可執行指令發送對所提議的功能的選擇的指示。
23.如權利要求17所述的計算機可讀媒質，其特徵在於，它還具有執行以下步驟的計算機可執行指令接收對所述第一系統步驟的建議的下一提議標識符；以及發送建議的下一提議標識符響應，其中，如果先前未投票贊成所述第一系統步驟，則所建議的下一提議標識符響應為空，並且其中，如果先前已投票贊成了所述第一系統步驟，則所建議的下一提議標識符響應包括對於對應所述第一系統步驟的先前投票贊成的值和先前投票贊成的提議標識符的指示。
24.如權利要求17所述的計算機可讀媒質，其特徵在於，它還具有執行以下步驟的計算機可執行指令接收對一可操作法定人數的提議、對所述可操作法定人數的提議的投票、第二提議標識符和第二步驟標識符，其中，對所述可操作法定人數的提議的投票提供足夠的信息，以確定所述分布式計算系統的第二法定人數是否已經在由所述第二步驟標識符標識的第二系統步驟中選擇了對所述可操作法定人數的提議；如果所述第二提議標識符大於或等於先前響應的提議標識符，則選擇對所述可操作法定人數的提議；以及發送對所述可操作法定人數的提議的選擇的指示。
25.如權利要求24所述的計算機可讀媒質，其特徵在於，所述分布式計算系統的第二法定人數包括第二發送裝置和第二接收裝置，其中，所述第二發送裝置發送對所述可操作法定人數的提議、對所述可操作法定人數的提議的投票、所述第二提議標識符和所述第二步驟標識符，並且其中，所述第二接收裝置接收對所述可操作法定人數的提議、對所述可操作法定人數的提議的投票、所述第二提議標識符和所述第二步驟標識符，並且其中，所述第二接收裝置是廉價計算裝置。
26.如權利要求24所述的計算機可讀媒質，其特徵在於，所述可操作法定人數包括所述分布式計算系統的第一法定人數，並且其中，所述第二系統步驟在所述第一系統步驟之前。
27.一種分布式計算系統中實現一分布式容錯一致同意算法的計算裝置，其特徵在於，所述計算裝置向第一接收計算裝置發送一提議的值、對所提議的值的投票、第一提議標識符和第一步驟標識符，其中，對所提議的值的投票令所述第一接收計算裝置能夠確定所述分布式計算系統的第一法定人數是否已經在由所述第一步驟標識符標識的第一系統步驟中選擇了所提議的值。
28.如權利要求27所述的計算裝置，其特徵在於，所述分布式計算系統的第一法定人數包括所述計算裝置和所述第一接收計算裝置。
29.如權利要求27所述的計算裝置，其特徵在於，它還向所述分布式計算系統中裝置的第二法定人數發送一對所述第一系統步驟的建議的下一提議標識符；以及從所述分布式計算系統中的第二法定人數裝置中的每一裝置接收一建議的下一提議標識符響應，其中，如果裝置的所述第二法定人數裝置中的每一裝置先前未投票贊成所述第一系統步驟，則所建議的下一提議標識符響應為空，並且其中，如果所述第二法定人數裝置中的每一裝置先前已投票贊成了所述第一系統步驟，則所建議的下一提議標識符響應包括對應於所述第一系統步驟的先前投票贊成的值和先前投票贊成的提議標識符的指示。
30.如權利要求29所述的計算裝置，其特徵在於，它選擇一大於所述先前投票贊成的提議標識符的任一個的標識符作為所述第一提議標識符；並且選擇所述先前投票贊成的值之一作為所提議的值。
31.如權利要求27所述的計算裝置，其特徵在於，它還發送對一可操作法定人數的提議、對所述可操作法定人數的提議的投票、第二提議標識符和第二步驟標識符，其中，對所述可操作法定人數的提議的投票令第二接收計算裝置能夠確定所述分布式計算系統的第二法定人數是否已經在由所述第二步驟標識符標識的第二系統步驟中選擇了對所述可操作法定人數的提議；並接收對所述可操作法定人數的提議的選擇的指示。
32.如權利要求31所述的計算裝置，其特徵在於，所述分布式計算系統的第二法定人數包括所述計算裝置和所述第二接收計算裝置，並且其中，所述第二接收計算裝置是廉價計算裝置。
33.一種在分布式計算系統中實現一分布式容錯意見一致算法的計算裝置，其特徵在於，所述計算裝置接收一提議的值、對所提議的值的投票、第一提議標識符和第一步驟標識符，其中，對所提議的值的投票令所述計算裝置能夠確定所述分布式計算系統的第一法定人數是否已經在由所述第一步驟標識符標識的第一系統步驟中選擇了所提議的值。
34.如權利要求33所述的計算裝置，其特徵在於，所述第一法定人數包括所述計算裝置和第一發送計算裝置，其中，所述第一發送計算裝置發送所提議的值、對所提議的值的投票、所述第一提議標識符和所述第一步驟標識符。
35.如權利要求33所述的計算裝置，其特徵在於，如果所述第一提議標識符大於或等於先前響應的提議標識符，則它還選擇所提議的值，並在不等候額外消息的情況下向原先提議所提議的值的客戶機計算裝置發送對所提議的值的選擇。
36.如權利要求33所述的計算裝置，其特徵在於，它還接收對所述第一系統步驟的建議的下一提議標識符；並發送一建議的下一提議標識符響應，其中，如果先前未投票贊成所述第一系統步驟，則所建議的下一提議標識符響應為空，並且其中，如果先前已投票贊成了所述第一系統步驟，則所建議的下一提議標識符響應包括對應於所述第一系統步驟的先前投票贊成的值和先前投票贊成的提議標識符的指示。
37.如權利要求33所述的計算裝置，其特徵在於，它還接收對一可操作法定人數的提議、對所述可操作法定人數的提議的投票、第二提議標識符和第二步驟標識符，其中，對所述可操作法定人數的提議的投票令所述計算裝置能夠確定所述分布式計算系統的第二法定人數是否已經在由所述第二步驟標識符標識的第二系統步驟中選擇了對所述可操作法定人數的提議；如果所述第二提議標識符大於或等於先前響應的提議標識符，則選擇對所述可操作法定人數的提議；並且發送對所述可操作法定人數的提議的選擇的指示。
38.如權利要求37所述的計算裝置，其特徵在於，所述分布式計算系統的第二法定人數包括所述計算裝置和第二發送裝置，其中，所述第二發送裝置發送對所述可操作法定人數的提議、對所述可操作法定人數的提議的投票、所述第二提議標識符和所述第二步驟標識符，並且其中，所述計算裝置是廉價計算裝置。
全文摘要
提出了一種用於以容錯方式操作分布式計算系統的簡化的容錯算法。一種包括三個計算裝置的系統只需令兩個裝置同意執行任何提議的功能。由此，當請求對提議的功能投票時，領導者裝置也可發送其對提議的功能的投票。這允許任何接收裝置用其自己的投票來形成所述法定人數。因此，任何接收裝置可在沒有任何進一步消息的情況下確定是否執行所提議的功能。此外，如果該裝置執行所提議的功能，它可直接向請求該功能的客戶機發送結果，從而了一個消息延遲。如果用於選擇並執行所提議的功能的裝置的法定人數本身由一法定人數選擇，則該系統的裝置之一可以是具有有限計算能力或存儲容量的廉價裝置。
文檔編號G06F11/00GK1690968SQ20041008219
公開日2005年11月2日 申請日期2004年12月30日 優先權日2003年12月30日
發明者L·B·蘭伯特 申請人:微軟公司