Problema del consenso

El problema del consenso es un problema fundamental de los sistemas distribuidos que consiste en poner de acuerdo a múltiples procesos en algo. Es el problema de averiguar como un conjunto de procesos de computación aislados que solo pueden comunicarse con mensajes se ponen de acuerdo sobre algo. El consenso es fácil en ausencia de fallos pero se convierte en algo difícil en escenarios intrincados de fallo con la presencia de canales imperfectos, caídas de participantes, violación de sincronizaciones o incluso cuando algunos de ellos pueden conspirar para que ese consenso no se produzca (comportamiento malicioso).

La solución a este tipo de problemas toma la forma de un algoritmo o protocolo (protocolo de consenso o algoritmo de consenso) y es usado por todos los procesos que no tienen un comportamiento malicioso.

Importancia

En general los sistemas distribuidos son propensos a fallos ya sea por caídas o por fallos intencionados (problema de los generales bizantinos). Para conseguir que los sistemas 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 replicar información. Replicando información el sistema es más fiable ya que 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 a 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​

Formalización

Supongamos que tenemos una colección de procesos $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 $p_{i}$ empieza en el estado de no decisión y propone un valor $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 $d_{i}$. Cuando lo hace, entra en el estado decidido, en el cual ya no se podrá cambiar $d_{i}$. Un algoritmo de consenso debería satisfacer las siguientes condiciones:​

• 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.

Ejemplos de protocolos de consenso

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