El consenso es un acuerdo general sobre una decisión tomada por la mayoría de los involucrados. Por ejemplo, el problema puede ser tan simple como amigos que intentan decidir qué restaurante tiene múltiples opciones para elegir o complejo como decisiones en sistemas distribuidos.
Necesidad de consenso en un sistema distribuido:
En un sistema distribuido, los Nodes se distribuyen a través de la red. Algunos de estos Nodes pueden fallar (falla de bloqueo) o comenzar a comportarse de manera anormal (falla bizantina). En tal escenario, se vuelve difícil llegar a una decisión común. Más concisamente,
- Hay n procesos, m de los cuales pueden estar defectuosos.
- La tarea es hacer que todos los procesos no defectuosos estén de acuerdo en algún valor, incluso en presencia de los procesos defectuosos.
Entonces podemos eliminar estos problemas dando las siguientes soluciones:
- Consenso sin culpa
- Consenso Con a lo sumo m Crash Faults
- Consenso con a lo sumo m fallas bizantinas
Consenso sin culpa alguna:
Estado de la red:
- Medio de comunicación confiable
- sistema síncrono
- Totalmente conectado
- El receptor siempre conoce la identidad del remitente de un mensaje.
Pasos:
- Cada proceso transmitirá su valor a todos los demás Nodes.
- Cada Node acordará el mínimo de todos los valores que recibe
- Como no hay falla, todos recibirán el mismo conjunto de valores y su mínimo será el mismo.
Consenso Con a lo sumo m fallas de choque:
Estado de la red:
- Medio de comunicación confiable
- sistema síncrono
- Totalmente conectado
- El receptor siempre conoce la identidad del remitente de un mensaje.
Pasos:
- Se necesitan al menos m+1 rondas para llegar a un consenso en dicho entorno.
- En la primera ronda, transmita su propio valor y, a partir de rondas sucesivas, transmita cualquier valor nuevo que el Node haya recibido en la última ronda.
- La falla de un Node puede ocurrir en el medio cuando comparte valores con los otros Nodes. Entonces, si la mayoría de los m Nodes pueden fallar, en el peor de los casos, un Node fallará cada vez que intentemos lograr un consenso.
- Y si cada Node pasa por m+1 rondas, entonces estamos seguros de que de estas m+1 seguramente habrá al menos una ronda cuando ningún Node haya fallado y todos obtengan todos los valores.
- Entonces, después de m+1 rondas, cada Node seleccionará el mínimo.
Consenso con a lo sumo m fallas bizantinas:
Fallas bizantinas: en términos simples, una falla bizantina es donde algunos Nodes comienzan a comportarse de manera maliciosa o anormal. Aquí el problema es que cualquiera de esos Nodes puede enviar dos valores diferentes a dos Nodes diferentes y, si eso sucede, todos nuestros métodos anteriores no funcionarán. Porque previamente estamos seguros de que si un Node envía un valor, enviará el mismo valor a todos los Nodes.
Estado de la red:
- Medio de comunicación confiable
- sistema síncrono
- Totalmente conectado
- El receptor siempre conoce la identidad del remitente de un mensaje.
- S es el conjunto de todos los Nodes.
- El Node que inicia el protocolo de acuerdo es el comandante
- El valor sugerido por el comandante es el orden
- Los otros Nodes, a los que el comandante envía la orden, son sus lugartenientes.
- OM significa Mensaje Oral y este término es solo para mostrar que un Node puede decir dos valores diferentes a dos Nodes diferentes.
Pasos:
- Mostraremos aquí un algoritmo recursivo llamado Algoritmo de Lamport-Shostak-Pease para resolver el Problema General Bizantino.
- Caso base- OM(0,S) :
- El comandante i envía el valor propuesto v a cada teniente j en S – {i}
- Cada teniente j acepta el valor v de i
- Caso recursivo- OM(m,S):
- El comandante i envía un valor v a cada teniente j ∈ S – {i}.
- Sea vj el valor que recibe el teniente j del comandante i, (0 si no recibe valor).
- El teniente j ahora inicia OM(m-1, S – {i}) con valor vj, como comandante. Al final de cada una de estas ejecuciones recursivas, cada lugarteniente leal j ∈ S – {i} ha acordado un conjunto de pares (k,vk), uno para cada k ∈ S – {i}.
- Después de que todos los lugartenientes hayan completado el Paso 3, cada lugarteniente j recopila los pares que recibió en el Paso 3 (su propio par contiene el valor original de su comandante y los otros pares contienen los valores devueltos por sus propios lugartenientes mediante la invocación recursiva de OM (m,S-{i}) )
- El cada teniente j conviene en el valor v = mayoría ( { (k,vk) | k ∈ S -{i} } ) que está en la mayoría de esos pares.
Aquí,
- Todas las soluciones discutidas hasta ahora son posibles cuando el sistema es síncrono, está completamente conectado y los Nodes conocen la identidad de cada uno.
- En el caso de fallas bizantinas, no hay solución posible si n < (3m + 1).
- En el modelo asíncrono, el consenso es imposible de lograr incluso con una sola falla de bloqueo.
- El consenso es imposible de lograr incluso con una sola falla de enlace, incluso en el modelo síncrono.
Hay algunos algoritmos de consenso más para entornos autorizados como RAFT , PAXOS. Además de la discusión anterior, hay algunos algoritmos de consenso más que se usan en entornos sin permiso, como Prueba de trabajo : se usa en Bitcoin.