Sobre el Consenso Mundial

SCP es una construcción para el acuerdo bizantino federado, un nuevo enfoque para el consenso.

¿Qué es el consenso distribuido?

En un sistema distribuido, todos los nodos deben actualizar periódicamente el estado que están replicando —por ejemplo, un libro mayor de transacciones. Identificamos cada actualización por un slot; un protocolo de consenso asegura que todos los nodos estén de acuerdo con el contenido del slot.

Cuando los nodos deciden que una actualización es segura para aplicar, ellos externalizan, o publican, la declaración acordada en su réplica del libro mayor. Consenso se alcanza cuando todos los nodos actualizan sus libros mayores y externalizan el mismo valor.

Tolerando el fallo bizantino

Queremos asegurar el consenso incluso cuando los nodos individuales actúan de manera arbitraria, comportamiento conocido como fallo bizantino. Para tolerar el fallo bizantino, SCP está diseñado para no requerir consentimiento unánime del conjunto completo de nodos para que el sistema alcance un acuerdo, y para tolerar nodos que mienten o envían mensajes incorrectos.

Rodajas de quórum: introduciendo la federación

En un sistema distribuido, un quórum es un conjunto de nodos suficiente para alcanzar un acuerdo. El acuerdo bizantino federado introduce el concepto de una rodaja de quórum, el subconjunto de un quórum que puede convencer a un nodo en particular del acuerdo.

Hay varias diferencias importantes entre el acuerdo bizantino tradicional no federado y el acuerdo bizantino federado. El acuerdo bizantino garantiza el consenso distribuido a pesar del fallo bizantino de los participantes. Sin embargo, requiere un acuerdo unánime sobre la membresía del sistema por parte de todos los participantes. Cada nodo en la red debe ser conocido y verificado de antemano.

FBA trae membresía abierta y control descentralizado al acuerdo bizantino. La diferencia clave entre un sistema de acuerdo bizantino y un sistema de acuerdo bizantino federado (FBAS) es que en FBA cada nodo elige sus propias rodajas de quórum. Los quórums a nivel del sistema resultan de estas decisiones de nodos individuales.

En FBA, no hay portero ni autoridad centralizada, por lo que los nodos individuales deciden qué otros participantes confían para obtener información. Los nodos pueden tener múltiples rodajas, y estas elecciones individuales de nodos pueden basarse en criterios extrínsecos. Por ejemplo, un banco en particular podría ser visto como reputado, haciendo que otros nodos requieran su reconocimiento de todas las transacciones; una empresa podría ya tener una relación financiera con una cooperativa de crédito y querer asegurarse de que tanto ella como el banco aprueben todas las transacciones.

Buenas rodajas de quórum comparten nodos y llevan a quórums que se superponen. Llamamos a esta superposición intersección de quórum. Cuando los quórums no se intersectan, terminamos con quórums disjuntos. Si los quórums son disjuntos, el quórum A puede, por ejemplo, acordar una declaración para pedir pizza, mientras que el quórum B puede acordar una declaración para pedir hamburguesas. Debido a que pueden acordar de manera independiente declaraciones contradictorias, los quórums disjuntos pueden socavar el consenso.

Tomando buenas decisiones

Cada nodo es responsable de asegurar que su elección de rodaja de quórum no viole la intersección de quórum. Tomar una decisión responsable generalmente se reduce a asegurar que las rodajas sean lo suficientemente grandes y que los nodos que contienen sean lo suficientemente importantes como para no arriesgar sus reputaciones mintiendo y proporcionando información diferente a diferentes personas.

Problemas en el camino hacia el acuerdo

En la selección de rodajas, los nodos deben mantener un equilibrio entre seguridad y vivacidad. Queremos que el sistema sea receptivo, pero no a expensas de la corrección.

• Los nodos carecen de vivacidad cuando se quedan bloqueados en el camino hacia el acuerdo, ralentizando el sistema.
• Los nodos carecen de seguridad cuando externalizan valores inconsistentes con aquellos externalizados en otros nodos, socavando el acuerdo a nivel del sistema. Tales nodos son divergentes.
• Un estado divergente ocurre cuando los libros mayores mantenidos por diferentes nodos almacenan estados contradictorios e irreconciliables. Un sistema bloqueado es menos peligroso que uno divergente.

Los nodos FBAS utilizan una técnica de votación federada para llegar a un acuerdo.

Consenso a la hora del almuerzo

Para describir con más detalle el proceso a través del cual un nodo vota por y eventualmente acepta una declaración, permitiendo que un sistema alcance un acuerdo, vamos a usar un ejemplo familiar para muchos. Digamos que un grupo de personas está votando qué ordenar para el almuerzo. En este ejemplo, todos los nombres de personas son nodos y todas las opciones de comida son declaraciones que los nodos necesitan considerar.

Vanessa trabaja en un espacio de coworking público donde es opcional ordenar el almuerzo con un grupo más grande. Hay una variedad de opciones, y no todos necesitan elegir algo; cuando suficiente del grupo ha decidido, hacen un pedido.

Vanessa y los compañeros de trabajo deciden resolver este problema usando SCP.

Votación inicial

Digamos que Vanessa quiere pizza pero necesita permanecer abierta en caso de que una gran parte del grupo vote por una de las otras opciones.

La votación es preliminar y solo ocurre a nivel de nodo. En el primer paso del proceso de votación federada, Vanessa vota para permanecer abierta a la posibilidad de aceptar pizza al afirmar que la pizza es válida y prometiendo que nunca ha votado ni votará individualmente por ninguna opción que contradiga a la pizza. Sin embargo, puede terminar aceptando algo diferente a la pizza si suficientes de sus compañeros de trabajo votan de otra manera (¡presión de grupo!).

Aceptación

Gracias a la intersección de quórum, las rodajas influyen unas en otras. Imagina un camino alternativo (indicado en el diagrama por “votó hamburguesa”), en el cual Vanessa inicialmente vota por hamburguesas. Pero recuerda, los votos son solo preliminares.

Si Winnie, Andrew y Eva están en rodajas de quórum con Vanessa, pueden bloquear el progreso de aceptar hamburguesas. Un conjunto de v-bloqueo de nodos contiene al menos un nodo de cada una de las rodajas de Vanessa y puede bloquear la acción en todos los quórums que contienen a Vanessa, haciendo que Vanessa acepte pizza en su lugar.

Vanessa realmente acepta pizza si:

1. nunca ha aceptado una declaración que contradiga a la pizza (por ejemplo, burritos), y
2. cada miembro de un conjunto de bloqueo v afirma aceptar pizza, o cada miembro de un quórum incluyendo a Vanessa vota por o afirma aceptar pizza

Ratificación

Cuando cada miembro de un quórum vota por pizza, decimos que el quórum ratifica la pizza. Un nodo no necesita ratificar una declaración de primera mano.

Por ejemplo, Scott a menudo confía en Andrew e Iris para decidir qué comer. Ellos son su quórum. Si todos tres votan por pizza, el quórum ha ratificado la pizza.

Un compañero de trabajo puede votar por una opción de almuerzo y luego aceptar una contradictoria. Votar por pizza no afirma la pizza como almuerzo — la pizza será aceptada como almuerzo solo si es ratificada.

Mensajes de confirmación

La confirmación es el paso final del proceso de votación e implica un acuerdo a nivel del sistema.

Para asegurar el acuerdo, los nodos intercambian mensajes de confirmación. Un sistema acuerda sobre una declaración si, una vez que se entregan y procesan suficientes mensajes, y sin importar qué eventos ocurran posteriormente, cada nodo receptivo y preciso aceptará la declaración.

Eva, por ejemplo, puede afirmar que ha aceptado pizza enviando el mensaje de confirmación, “aceptar(pizza).” Este mensaje es una abreviatura de “He aceptado pizza.”

Cuando Eva envía este mensaje de confirmación, Winnie, Andrew y Graydon, las otras personas en su quórum, transmiten “aceptar(pizza).”

Estos mensajes pueden convencer a personas adicionales para aceptar pizza. Como en el ejemplo de aceptación anterior, si Vanessa inicialmente vota por una opción que contradice a la pizza, como hamburguesas, aún puede aceptar pizza si un conjunto de bloqueo v la acepta. Estas personas adicionales convencen a tantos otros como sea posible, transmitiendo “aceptar(pizza)” hasta un punto en el que todos los que pueden aceptar pizza la han aceptado.

Un quórum subsiguiente de mensajes de confirmación permite a Vanessa confirmar pizza, lo que implica que el sistema está de acuerdo con la pizza. La empresa pide pizza. Todos están felices.

El Protocolo: SCP

SCP asume el principal desafío del consenso distribuido: el sistema no puede estar de acuerdo con una declaración sin el riesgo de quedar bloqueado y perder vivacidad.

Es posible que una declaración quede atrapada en un estado permanentemente indeterminado antes de que el sistema alcance un acuerdo sobre ella. El objetivo de SCP es minimizar tal bloqueo y el potencial de divergencia. Por lo tanto, el protocolo formula declaraciones de manera que sea posible neutralizar declaraciones bloqueadas si se quedan atascadas en el proceso de votación — toda esta magia se basa en un enfoque basado en votos para el problema.

Un voto es un referéndum sobre el valor asociado con el voto, es decir, “¿Cuál es el valor por el que estamos votando?” El enfoque basado en votos significa que, para eventualmente externalizar un valor, un nodo debe comprometer el voto ligado a ese valor.

Comprometer o abortar

Cada nodo puede comprometer o abortar cualquier voto. Para volver a la analogía del pedido de almuerzo, el grupo de compañeros de trabajo podría quedarse atascado, sin poder llegar a un acuerdo. Necesitamos una manera de neutralizar una opción — digamos, hamburguesas — si el equipo se queda atascado en ella para que puedan avanzar y eventualmente hacer un pedido.

Para neutralizar las hamburguesas como opción, los compañeros de trabajo aceptan “abortar hamburguesas,” las hamburguesas se vuelven irrelevantes, y el grupo avanza para votar por otra opción de almuerzo.

Si, por otro lado, los compañeros de trabajo ratifican la declaración “comprometer pizza,” entonces el grupo estará de acuerdo con el valor, pizza, ligado a ese voto. Una declaración “comprometer pizza” es válida, y por lo tanto puede aparecer legítimamente en votos, solo si todos los votos incompatibles menores que pizza han sido abortados.

En un sistema SCP con intersección de quórum, no hay estados bloqueados para nodos intactos. Siempre hay una secuencia de eventos a través de la cual los nodos intactos pueden llegar a un acuerdo sobre y comprometer un valor.

Si los nodos dependen demasiado de nodos malos, se les llama contaminados. En un FBAS, los nodos contaminados forman un conjunto prescindible, lo que significa que los nodos intactos pueden ratificar declaraciones sin la cooperación de nodos contaminados y los nodos contaminados no pueden socavar el acuerdo entre nodos intactos. Si ningún nodo intacto ha votado comprometer ningún voto, entonces pueden avanzar a cualquier voto más alto que cualquier voto que hayan prometido abortar. La falta de respuesta de nodos contaminados no impedirá que los nodos intactos formen quórum y progresen.

El protocolo demuestra que podemos llegar a un acuerdo y ordenar el almuerzo, pero ¿qué pasa si un montón de personas votan por cosas diferentes y ningún quórum ratifica alguna opción? Esta pregunta — un voto dividido — es precisamente por qué necesitamos asociar cada opción de almuerzo con un voto. El proceso de votación, incluido cómo tratar escenarios como votos divididos, es intrincado y contiene detalles no descritos aquí. Para una descripción más completa, así como teoremas y pruebas, lee el documento técnico.

Este resumen cubre los puntos principales y la terminología de “El Protocolo de Consenso de Stellar: Un Modelo Federado para el Consenso a Nivel de Internet,” un documento técnico por el Prof. David Mazières, Científico Jefe en Stellar Development Foundation.

¿Preguntas? Hazlas en StackExchange.