Byzantine fault tolerant architecture for geographically distributed graph databases

Abstract

Juntamente com o aumento do número de usuários da Internet, o tamanho de dados e suas conexões cresceram substancialmente nas últimas décadas, o que levou o Big Data a ser um dos principais tópicos em ciência da computação. Devido a isso, iniciaram-se pesquisas buscando oferecer serviços altamente disponíveis com tempos de resposta curtos na area de dados altamente conectados, o que levou ao desenvolvimento das bases de dados de grafos de hoje.Infelizmente, para as bases de dados de grafos mais comuns NoSQL apenas algumas soluções para tolerância a faltas foram propostas, porém faltas bizantinas, as quais podem afetar a consistência de todo o sistema, não receberam nenhuma atenção no campo de bancos de dados de grafos distribuídos. Este trabalho, portanto, propõe um algoritmo de tolerância a faltas bizantinas na área de bancos de dados de grafos. Devido às preocupações de desempenho no campo da tolerância a faltas, também propomos uma arquitetura hierárquica flexível capaz de tolerar faltas bizantinas com uma sobrecarga de desempenho significativamente menor no caso de uso típico em comparação com a arquitetura plana.

Abstract : Along with the increase of Internet user numbers, data sizes and their connections grew massively in the last few decades, Big Data emerged as one of the main topics in computer science. Due to this development, concerns raised on how to offer highly available services with short response times in the field of highly connected data. This caused the development of today's graph databases.Unfortunately, the most common NoSQL graph databases have not received much attention of researchers yet and only a few solutions for fault tolerance have been proposed in this area. But, Byzantine failures, which may affect the consistency of the whole system, haven't found any attention at all in the field of distributed graph databases. This work, therefore, proposes a solution which implements an algorithm for Byzantine fault tolerance in the area of graph databases. Due to the performance concerns in the field of fault tolerance, we also propose a flexible hierarchical architecture which is able to endure Byzantine failures with a significantly lower performance overhead in the typical use-case compared to the flat counterpart.