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 cómo 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.

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]​

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:

---