Thesis : Byzantine Fault-tolerance in dynamic networksPhD school thesis
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.  for a limited set of (unpractical) dynamic networks. Another aproach by Dobrev et al.  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