# Thesis : Byzantine Fault-tolerance in dynamic networks

PhD school thesis
The first challenge to solve is a tractable Byzantine broadcast algorithm. Although the condition pro- vided by Maurer et al. [16] is the best possible from a theoretical point of view, it lacks practicality. That is, verifying their condition requires to run at each node upon each message reception an exponential time algorithm to compute the minimal node-cut of the received paths attached to received messages. As our preliminary results suggest that computing the minimal dynamic cut in dynamic networks using received paths attached to messages is at least NP-complete, one option is to investigate approxima- tion algorithms. However, as we do not want to compromise safety, the approximation should always be lower than the actual minimal dynamic cut. One trivial such approximation is the number of node disjoint-paths among the received paths, but there exist dynamic networks where no two dynamic paths are node-disjoint [11], so the computed dynamic minimal cut would be 1, resulting in no genuine mes- sage being delivered even if at most one Byzantine node is in the network, that is, a loss of liveness.

Scientific lock: Overall, to date, for dynamic networks, no tractable (that is, polynomial) solution exists for reliable communication with Byzantine attacks.

Designing a polynomial approximation for the dynamic minimal cut problem that compromises neither safety nor liveness of the resulting broadcast algorithm is an obvious first goal.

The second goal is to investigate the orthogonal approach of using a purely local Byzantine-resilient broadcast algorithm, that is, an algorithm that does not store traversed paths with each message. In static networks, this approach was promoted as the Certified Propagation Algorithm (CPA) [12, 20, 21]: if sufficiently many neighbors broadcast the same message, then it is safe to rebroadcast it. For example, if at most k Byzantine nodes can be neighbors of a particular node, then it is safe to rebroadcast it once received k + 1 copies of the same message from different neighbors. Of course, the necessary and sufficient conditions induced by local algorithms are different from the global ones (we go from a global requirement on the number of Byzantine attackers to a local requirement about the neighborhood of each node), but not necessarily less useful as they are intrinsically polynomial locally. A first step in this direction was initiated by Bonomi et al. [5] for a limited set of (unpractical) dynamic networks. Another aproach by Dobrev et al. [8] consider the broadcast problem in the context of dynamic edge faults, that are a strict subset of Byzantine failures. So, our second goal in this task will be to fully characterize the CPA approach in dynamic networks. This is likely to promote a new set of lower and upper bounds, expressed with local metrics, for polynomial broadcast algorithms.

Scientific lock: Overall, to date, for dynamic networks, no tractable (that is, polynomial) solution exists for reliable communication with Byzantine attacks.

Designing a polynomial approximation for the dynamic minimal cut problem that compromises neither safety nor liveness of the resulting broadcast algorithm is an obvious first goal.

The second goal is to investigate the orthogonal approach of using a purely local Byzantine-resilient broadcast algorithm, that is, an algorithm that does not store traversed paths with each message. In static networks, this approach was promoted as the Certified Propagation Algorithm (CPA) [12, 20, 21]: if sufficiently many neighbors broadcast the same message, then it is safe to rebroadcast it. For example, if at most k Byzantine nodes can be neighbors of a particular node, then it is safe to rebroadcast it once received k + 1 copies of the same message from different neighbors. Of course, the necessary and sufficient conditions induced by local algorithms are different from the global ones (we go from a global requirement on the number of Byzantine attackers to a local requirement about the neighborhood of each node), but not necessarily less useful as they are intrinsically polynomial locally. A first step in this direction was initiated by Bonomi et al. [5] for a limited set of (unpractical) dynamic networks. Another aproach by Dobrev et al. [8] consider the broadcast problem in the context of dynamic edge faults, that are a strict subset of Byzantine failures. So, our second goal in this task will be to fully characterize the CPA approach in dynamic networks. This is likely to promote a new set of lower and upper bounds, expressed with local metrics, for polynomial broadcast algorithms.

*This PhD research project has been submitted for a funding request to “Ecole Doctorale d‘Informatique, Télécommunication et d‘Electronique (EDITE)”. The PhD candidate selected by the project leader will therefore participate in the project selection process (including a file and an interview) to obtain funding.*

Contact :Sébastien Tixeuil