A Recursive Byzantine-Resilient Protocol
學年 103
學期 2
出版（發表）日期 2015-02-01
作品名稱 A Recursive Byzantine-Resilient Protocol
作品名稱（其他語言）
著者 Cheng, Chien-Fu; Tsai, Kuo-Tang
單位
出版者
著錄名稱、卷期、頁數 Journal of Network and Computer Applications 48, p.87-98
摘要 To solve the consensus problem, the classical consensus protocols require t+1 rounds of message exchange to tolerate t faulty processors, where t=⌊(n−1)/3⌋ and n is the total number of processors in the network. With advancement of software and hardware technologies in recent years, the “actual number of faulty processors” (fact) in a network is usually smaller than t, and fact≪t. However, the classical consensus protocols still need to execute t+1 rounds of message exchange even if there are no faulty processors in the network. To address this issue, we propose a new consensus protocol called Recursive Byzantine-Resilient protocol (RBR protocol). We integrate the concepts of parallel computing, grouping, hierarchy and recursion into this protocol to reduce its time and space complexity. Specifically, the RBR protocol can solve the consensus problem in the presence of 2h(⌊((n/4h)−1)/3⌋+1)−1 Byzantine faulty processors, where h=⌊(lg(n)−2)/2⌋. The time complexity and space complexity of RBR protocol are O(lg(n)) and O(nklg(n)) respectively. The results reveal that RBR protocol outperforms previous protocols in terms of time complexity and in terms of space complexity. In this paper, we also discuss how to enhance the fault-tolerance capability of RBR protocol in achieving consensus through repetitive execution of the protocol when the number of Byzantine faulty processors is greater than 2h(⌊((n/4h)−1)/3⌋+1)−1.
關鍵字 Distributed system;Fault-tolerant;Consensus problem;Byzantine fault
語言 en
ISSN 1095-8592
期刊性質 國外
收錄於 SCI EI
產學合作
通訊作者 Cheng, Chien-Fu
審稿制度 是
國別 GBR
公開徵稿
出版型式 ,電子版,紙本
相關連結

機構典藏連結 ( http://tkuir.lib.tku.edu.tw:8080/dspace/handle/987654321/104259 )