# Improved Connectivity Condition for Byzantine Fault Tolerance

arXiv: https://arxiv.org/abs/1503.02774 · HTML: https://mlsanity.com/paper/1503.02774/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Mar 2015.

## Built on by (most cited first, 1 of 1)

- [Impact of Network Topology on Byzantine Resilience in Decentralized Federated Learning](https://mlsanity.com/paper/2407.05141/) (2024)

## Abstract (arXiv)

Given a network in which some pairs of nodes can communicate freely, and some subsets of the nodes could be faulty and colluding to disrupt communication, when can messages reliably be sent from one given node to another? We give a new characterization of when the agreement problem can be solved and provide an agreement algorithm which can reach agreement when the number of Byzantine nodes along each minimal vertex cut is bounded. Our new bound holds for a strict superset of cases than the previously known bound. We show that the new bound is tight. Furthermore, we show that this algorithm does not require the processes to know the graph structure, as the previously known algorithm did. Finally, we explore some of the situations in which we can reach agreement if we assume that individual nodes or entire subgraphs are trustworthy.