Timing analysis of leader-based and decentralized Byzantine consensus algorithms

Brazilian Computer Society. Journal

Fatemeh Borran¹  Schiper²  Martin Hutle³  André⁴ 

[1] Ecole Polytechnique FéFraunhofer AISEC, Garching near Munich, Germany;dérale de Lausanne (EPFL), Lausanne, Switzerland

关键词: Distributed algorithms;    Fault tolerance;    Byzantine consensus;    Timing analysis;   

DOI  :  10.1007/s13173-012-0058-6

学科分类：农业科学（综合）

来源: Springer U K

【 摘 要 】

We consider the Byzantine consensus problem in a partially synchronous system with strong validity. For this problem, two main algorithms—with different resilience—are described in the literature. These two algorithms assume a leader process. A decentralized variant (variant without leader) of these two algorithms has also been given in a previous paper. Here, we compare analytically, in a round-based model, the leader-based variant of these algorithms with the decentralized variant. We show that, in most cases, the decentralized variant of the algorithm has a better worst-case execution time. Moreover, for the practically relevant case t≤2 (where t is the maximum number of Byzantine processes), this worst-case execution time is even at least as good as the execution time of the leader-based algorithms in fault-free runs.

【 授权许可】

CC BY