State machine replication: exploring a path to build reliable services

Abstract

Hoy en día disfrutamos de los beneficios de un mundo digital el cual nos brinda una creciente variedad de servicios. La alta disponibilidad de estos servicios es un aspecto importante y es posible gracias a la capacidad para tolerar fallas de los sistemas distribuidos. En este contexto los protocolos state machine replication (SMR) desempeñan un rol fundamental para implementar este tipo de servicios. Motivados por la importancia de los protocolos SMR, en este trabajo brindamos los fundamentos para comprender su funcionamiento y mostramos la alta complejidad inherente a estos protocolos así como sus principales causas y desafíos asociados. Producto de una revisión crítica de la literatura, identificamos una brecha de investigación de un nuevo método llamado RABIA, el cual tiene como objetivo simplificar el esfuerzo de implementación de un protocolo SMR utilizando la randomización en su algoritmo de consenso. Planteamos como propuesta profundizar el estudio de RABIA mediante un caso de estudio de implementación de un servicio de almacenamiento tipo llave-valor con capacidad de tolerancia a fallos y garantizando la consistencia de datos.

Currently we enjoy the benefits of a digital world that provides us with an increasing variety of services. The high availability of these services is an important aspect and is made possible by the fault tolerance of distributed systems. In this context, state machine replication protocols (SMR) play a fundamental role in implementing this type of services. Motivated by the importance of SMR protocols, in this paper we provide the fundamentals to understand their operation and show the high complexity inherent to these protocols as well as their main causes and associated challenges. As a result of a critical literature review, we identified a research gap for a new approach called RABIA, which aims to simplify the implementation effort of an SMR protocol by taking advantage of randomization in the consensus algorithm. We propose to deepen the study of RABIA by means of a case study which requires the implementation of a store layer based on keyvalue to offer a fault-tolerant service that guarantees data consistency.