Borran, F.F.BorranHutle, M.M.HutleSchiper, A.A.Schiper2022-03-042022-03-042012https://publica.fraunhofer.de/handle/publica/23128210.1007/s13173-012-0058-62-s2.0-84870358418We 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 t2 (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.enjournal article