Byzantine Fault Tolerant protocols are complicated and hard to implement.Today’s software industry is reluctant to adopt these protocols because of thehigh overhead of message exchange in the agreement phase and the high resourceconsumption necessary to tolerate faults (as 3 f + 1 replicas are required totolerate f faults). Moreover, total ordering of messages is needed by mostclassical protocols to provide strong consistency in both agreement and executionphases. Research has improved throughput of the execution phase by introducingconcurrency using modern multicore infrastructures in recent years. However,improvements to the agreement phase remains an open area. Byzantine Fault Tolerant systems use State Machine Replication to tolerate awide range of faults. The approach uses leader based consensus algorithms for thedeterministic execution of service on all replicas to make sure all correct replicasreach same state. For this purpose, several algorithms have been proposed toprovide total ordering of messages through an elected leader. Usually, a singleleader is considered to be a bottleneck as it cannot provide the desired throughputfor real-time software services. In order to achieve a higher throughput there is aneed for a solution which can execute multiple consensus rounds concurrently. We present a solution that enables multiple consensus rounds in parallel bychoosing multiple leaders. By enabling concurrent consensus, our approach canexecute several requests in parallel. In our approach we incorporate applicationspecific knowledge to split the total order of events into multiple partial orderswhich are causally consistent in order to ensure safety. Furthermore, a dependencycheck is required for every client request before it is assigned to a particular leaderfor agreement. This methodology relies on optimistic prediction of dependenciesto provide higher throughput. We also propose a solution to correct the course ofexecution without rollbacking if dependencies were wrongly predicted. Our evaluation shows that in normal cases this approach can achieve upto 100% higher throughput than conventional approaches for large numbers ofclients. We also show that this approach has the potential to perform better incomplex scenarios

A mesure que les réseaux s'étendent, ils deviennent de plus en plus susceptibles de défaillir. En effet, leurs nœuds peuvent être sujets à des attaques, pannes, corruptions de mémoire... Afin d'englober tous les types de fautes possibles, nous considérons le modèle le plus général possible : le modèle Byzantin, où les nœuds fautifs ont un comportement arbitraire (et donc, potentiellement malveillant). De telles fautes sont extrêmement dangereuses : un seul nœud Byzantin, s'il n'est pas neutralisé, peut déstabiliser l'intégralité du réseau.Nous considérons le problème d'échanger fiablement des informations dans un réseau multi-Sauts malgré la présence de telles fautes Byzantines. Des solutions existent mais nécessitent un réseau dense, avec un grand nombre de voisins par nœud. Dans cette thèse, nous proposons des solutions pour les réseaux faiblement connectés, tels que la grille, où chaque nœud a au plus 4 voisins. Dans une première partie, nous acceptons l'idée qu'une minorité de nœuds corrects échouent à communiquer fiablement. En contrepartie, nous proposons des solutions qui tolèrent un grand nombre de fautes Byzantines dans les réseaux faiblement connectés. Dans une seconde partie, nous proposons des algorithmes qui garantissent une communication fiable entre tous les nœuds corrects, pourvu que les nœuds Byzantins soient suffisamment distants. Enfin, nous généralisons des résultats existants à de nouveaux contextes : les réseaux dynamiques, et les réseaux de taille non-Bornée. / As modern networks grow larger and larger, they become more likely to fail. Indeed, their nodes can be subject to attacks, failures, memory corruptions... In order to encompass all possible types of failures, we consider the most general model of failure: the Byzantine model, where the failing nodes have an arbitrary (and thus, potentially malicious) behavior. Such failures are extremely dangerous, as one single Byzantine node, if not neutralized, can potentially lie to the entire network. We consider the problem of reliably exchanging information in a multihop network despite such Byzantine failures. Solutions exist but require a dense network, where each node has a large number of neighbors. In this thesis, we propose solutions for sparse networks, such as the grid, where each node has at most 4 neighbors. In a first part, we accept that some correct nodes fail to communicate reliably. In exchange, we propose quantitative solutions that tolerate a large number of Byzantine failures, and significantly outperform previous solutions in sparse networks. In a second part, we propose algorithms that ensure reliable communication between all correct nodes, provided that the Byzantine nodes are sufficiently distant from each other. At last, we generalize existing results to new contexts: dynamic networks, and networks with an unbounded diameter.