2015/05/16 by Hammurabi Mendes, Maurice Herlihy, Mendes, Hammurabi +1
Computer Science · #Advanced Data Storage Technologies #Distributed #Distributed systems and fault tolerance #FOS: Computer and information sciences #Parallel #Petri Nets in System Modeling #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.1505.04224
openalex publication_date 2015/05/16 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28
In this paper, we show that the protocol complex of a Byzantine synchronous system can remain (k - 1)-connected for up to \lceil t/k \rceil rounds, where t is the maximum number of Byzantine processes, and t ≥ k ≥ 1. This topological property implies that \lceil t/k \rceil + 1 rounds are necessary to solve k-set agreement in Byzantine synchronous systems, compared to \lfloor t/k \rfloor + 1 rounds in synchronous crash-failure systems. We also show that our connectivity bound is tight as we indicate solutions to Byzantine k-set agreement in exactly \lceil t/k \rceil + 1 synchronous rounds, at least when n is suitably large compared to t. In conclusion, we see how Byzantine failures can potentially require one extra round to solve k-set agreement, and, for n suitably large compared to t, at most that.