Reconocimiento de familias hereditarias en el modelo Congested Clique en presencia de nodos bizantinos

Abstract

En un sistema distribuido, un nodo bizantino es un nodo participante en el sistema que intenta dañar su funcionamiento intencionalmente; por ejemplo, al no reenviar mensajes a otros participantes. En esta tesis se estudian algoritmos distribuidos en presencia de nodos bizantinos. En la Introducción se presenta el contexto donde nace la problemática principal a estudiar. En el primer capítulo se precisan los principales resultados teóricos ya conocidos, con énfasis en los resultados del paper Byzantine connectivity testing in the congested clique de Agustine et al. En ese trabajo, con la introducción de la noción de comité, se sientan las bases sobre cómo desarrollar algoritmos distribuidos en presencia de nodos bizantinos. En el segundo capítulo se exploran las ideas y conceptos básicos para abordar esta tesis. En el tercer capítulo se estudia el reconocimiento de grafos k-degenerados. En el cuarto capítulo se generaliza este resultado extendiéndolo a cualquier familia de grafos hereditaria, dando no sólo un algoritmo que estudia el reconocimiento de estas familias en presencia de nodos bizantinos, sino que también mostrando que no existe mejor resultado posible alcanzado por dicho algoritmo