Problema del consenso

En general, los sistemas distribuidos son propensos a fallos ya sea por caídas o fallos intencionados (problema de los generales bizantinos). Para conseguir que los sistemas sean más fiables se intenta que sean lo más tolerantes frente a dichos fallos. Una de las estrategias más habituales para conseguirlo es mediante la réplica de información. El sistema de réplica de información es fiable pues la información reside en varios nodos. Sin embargo, es un reto mantener la consistencia entre los nodos que comparten información a la vez en un entorno en el que puede haber fallos (sistema tolerante de fallos). De esto se encargan los algoritmos o protocolos de consenso.

Por ejemplo: supongamos una base de datos distribuida que replica un estado común. Para mantener el estado consistente, cada réplica tiene que aplicar las mismas operaciones en el mismo orden para que su copia del estado sea consistente con el resto. Por tanto habrá un protocolo de consenso que tratará de mantener el estado consistente entre las múltiples réplicas conectadas asíncronamente no confiables[1]

Supongamos que tenemos una colección de procesos ${\displaystyle p_{i}(i=1,2...N)}$ los cuales se comunican por paso de mensajes. El objetivo es llegar a consenso aunque haya fallos (por ejemplo comunicaciones no fiables o fallos en los procesos). Para llegar a un consenso, cada proceso ${\displaystyle p_{i}}$ empieza en el estado de no decisión y propone un valor ${\displaystyle v_{i}}$. Los procesos se comunican unos con otros intercambiando valores siguiendo un protocolo (protocolo de consenso). A continuación, cada proceso fija un valor en una variable de decisión ${\displaystyle d_{i}}$. Cuando lo hace, entra en el estado decidido, en el cual ya no se podrá cambiar ${\displaystyle d_{i}}$. Un algoritmo de consenso debería satisfacer las siguientes condiciones:[2]

• Finalización: Cada proceso correcto debe acabar asignando un valor a su variable de decisión.
• Acuerdo: El valor finalmente decidido por todos los procesos correctos es el mismo.
• Integridad: Si todos los procesos correctos han propuesto el mismo valor, entonces cualquier proceso correcto en el estado de decisión ha elegido este valor.

Se han elaborado distintos protocolos o algoritmos que solucionan este tipo de problemas. Cada uno se aplica para cierto tipo de entornos y tienen sus propias características. Veamos algunos ejemplos:

• Commit de dos fases
• Commit de tres fases
• Raft
• Paxos y Multipaxos
• Prueba de trabajo
• Prueba de participación tanto en su versión original como en la versión prueba de participación delegada.
• Prueba de quemadura
• Algoritmo de consenso Protocolo Ripple. Es el usado en Ripple y Stellar
• Zookeeper Atomic Broadcast
• Viewstamped replication