Dual Fallible Consensus in a Scale Free Network

Abstract

在分散式系統中，當要執行一些特定的任務時，必須事先達成一個共同的合議，當合議達成後分散式系統可以對抗損毀元件的影響，而這種問題稱為合議問題。合議問題可以使運作健全的處理器排除掉損毀元件的影響而達成協議，並且增加工作執行的可靠度。過去有關合議問題的研究中，大都是在隨機式的網路中進行，然而現今實際的網路環境卻是異常複雜且呈現無尺度之架構。因此本研究將在一個更符合目前以及未來需求的無尺度網路架構下，尋找出最快以及容錯能力最好且可達成合議的方法。透過無尺度網路所具有的成長性和優先連結性，將使合議問題的實用性及適用性大增

Generally, the task in a distributed system must achieve consensus. It requires a set of processors to agree on a common value even if some components are corrupted. There are significant studies on this consensus problem in a random network. Recently, many large complex networks have emerged and displayed a scale-free feature, which influences the system to reach a common value differently. Unfortunately, existing consensus protocols and results cannot cope with the new network environment and the consensus problem thus needs to be revisited. In this paper, we propose a new consensus protocol to adapt to the scale-free network environment and derive its bound of allowable faulty transmission media (TMs) with two rounds of message exchange. It is observed that the scale-free network with the proposed consensus protocol can tolerate more faulty TMs than the networks based on previous studies.