淡江大學機構典藏:Item 987654321/104259
English  |  正體中文  |  简体中文  |  Items with full text/Total items : 62822/95882 (66%)
Visitors : 4025133      Online Users : 1040
RC Version 7.0 © Powered By DSPACE, MIT. Enhanced by NTU Library & TKU Library IR team.
Scope Tips:
  • please add "double quotation mark" for query phrases to get precise results
  • please goto advance search for comprehansive author search
    •  Adv. Search
    Home ‧ Login ‧ Upload ‧ Help ‧ About ‧ Administer Goto mobile version


    Please use this identifier to cite or link to this item: https://tkuir.lib.tku.edu.tw/dspace/handle/987654321/104259


    Title: A Recursive Byzantine-Resilient Protocol
    Authors: Cheng, Chien-Fu;Tsai, Kuo-Tang
    Keywords: Distributed system;Fault-tolerant;Consensus problem;Byzantine fault
    Date: 2015-02
    Issue Date: 2016-01-06 10:53:16 (UTC+8)
    Abstract: 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.
    Relation: Journal of Network and Computer Applications 48, pp.87-98
    DOI: 10.1016/j.jnca.2014.10.010
    Appears in Collections:[Graduate Institute & Department of Computer Science and Information Engineering] Journal Article

    Files in This Item:

    File Description SizeFormat
    A recursive Byzantine-resilient protocol.pdf1858KbAdobe PDF2View/Open
    index.html0KbHTML214View/Open

    All items in 機構典藏 are protected by copyright, with all rights reserved.

    DSpace Software Copyright © 2002-2004  MIT &  Hewlett-Packard  /   Enhanced by   NTU Library & TKU Library IR teams. Copyright ©   - Feedback