Équivalence du Consensus et de la Diffusion dans les Réseaux à Omissions Bornées

International audienceNous comparons l'existence de solutions pour le problème du Consensus ou le problème de la Diffusion dans le cadre de réseaux de communication synchrones où la transmission de message n'est pas fiable. Certains messages peuvent être perdus et à chaque ronde le nombre de messages perdus est borné d'une certaine manière. Nous montrons que dans ce cas, et quelle que soit la manière de compter les pertes (localement, globalement,...) le problème du Consensus est équivalent au problème de la Diffusion tant en terme de calculabilité qu'en terme de complexité