Greft: uma arquitetura para processamento distribuído de grafos de larga escala tolerante a faltas

Abstract

Grafos são usados para modelar um grande número de problemas reais em áreas como aprendizado de máquina e mineração de dados. O crescimento das bases de dados destas áreas tem levado à criação de uma variedade de sistemas distribuídos para processamento de grafos muito grandes, dentre os quais se destaca o Pregel, da Google. Embora esses sistemas costumem ser tolerantes a faltas de parada, a literatura sugere que eles também estão suscetíveis a faltas arbitrárias acidentais. Neste trabalho é apresentado Greft, uma arquitetura para processamento distribuído de grafos de larga escala capaz de lidar com essas faltas, baseado no Graph Processing System (GPS), uma implementação de código aberto do Pregel. São apresentados também resultados experimentais do protótipo obtidos na Amazon Web Services (AWS), onde demonstra-se que este algoritmo usa o dobro de recursos do original, em vez de 3 ou 4 vezes, como é comum em modelos tolerantes a faltas Bizantinas. Com isso, seu custo torna-se aceitável para aplicações críticas que requerem esse nível de tolerância a faltas.<br>

Abstract : Graphs are used to model a large number of real problems in areas such as machine learning and data mining. The increasing dataset sizes has led to the creation of various distributed large scale graph processing systems, among which Google's Pregel stands out. Although these systems usually tolerate crash faults, literature suggests they are vulnerable to accidental arbitrary faults as well. In this dissertation we present the architecture, algorithms and a prototype of such system that can tolerate this kind of fault, based on Graph Processing System (GPS), an open source implementation of Pregel. Experimental results of the prototype in Amazon Web Services (AWS) are presented, showing that it uses twice the resources of the original implementation, instead of 3 or 4 times as usual in Byzantine fault-tolerant systems. This cost is acceptable for critical applications that require this level of fault tolerance.