Un problema fundamental en la computación distribuida y los sistemas multiagente es lograr la confiabilidad general del sistema en presencia de una serie de procesos defectuosos. Esto a menudo requiere coordinar procesos para llegar a un consenso o acordar algún valor de datos que se necesita durante el cálculo. Ejemplos de aplicaciones de consenso incluyen acordar qué transacciones enviar a una base de datos y en qué orden, replicación de máquinas de estado y transmisiones atómicas . Las aplicaciones del mundo real que a menudo requieren consenso incluyen computación en la nube , sincronización de relojes , PageRank , formación de opinión, redes eléctricas inteligentes , estimación de estado , control de vehículos aéreos no tripulados (y múltiples robots/agentes en general), equilibrio de carga , blockchain y otras.
El problema del consenso requiere un acuerdo entre varios procesos (o agentes) sobre un único valor de datos. Algunos de los procesos (agentes) pueden fallar o no ser confiables de otras maneras, por lo que los protocolos de consenso deben ser tolerantes a fallas o resilientes. Los procesos deben presentar sus valores candidatos, comunicarse entre sí y acordar un valor único de consenso.
El problema del consenso es un problema fundamental en el control de sistemas multiagente. Un enfoque para generar consenso es que todos los procesos (agentes) acuerden un valor mayoritario. En este contexto, una mayoría requiere al menos uno más de la mitad de los votos disponibles (donde a cada proceso se le da un voto). Sin embargo, uno o más procesos defectuosos pueden distorsionar el resultado resultante, de modo que es posible que no se alcance un consenso o que se logre de manera incorrecta.
Los protocolos que resuelven problemas de consenso están diseñados para abordar un número limitado de procesos defectuosos . Estos protocolos deben cumplir varios requisitos para ser útiles. Por ejemplo, un protocolo trivial podría hacer que todos los procesos generen el valor binario 1. Esto no es útil; por lo tanto, el requisito se modifica de manera que la producción debe depender del insumo. Es decir, el valor de salida de un protocolo de consenso debe ser el valor de entrada de algún proceso. Otro requisito es que un proceso pueda decidir sobre un valor de salida sólo una vez, y esta decisión es irrevocable. Un método es correcto en una ejecución si no experimenta un fallo. Un protocolo de consenso que tolere los fallos de detención debe satisfacer las siguientes propiedades. [1]
Según la solicitud, pueden ser apropiadas variaciones en la definición de integridad . Por ejemplo, un tipo de integridad más débil [ se necesita más explicación ] sería que el valor de la decisión igualara un valor propuesto por algún proceso correcto, no necesariamente todos. [1] También existe una condición conocida como validez en la literatura que se refiere a la propiedad de que un mensaje enviado por un proceso debe ser entregado. [1]
Un protocolo que puede garantizar correctamente el consenso entre n procesos de los cuales t fallan como máximo se dice que es t-resiliente .
Al evaluar el desempeño de los protocolos de consenso, dos factores de interés son el tiempo de ejecución y la complejidad del mensaje . El tiempo de ejecución se da en notación Big O en el número de rondas de intercambio de mensajes en función de algunos parámetros de entrada (normalmente el número de procesos y/o el tamaño del dominio de entrada). La complejidad del mensaje se refiere a la cantidad de tráfico de mensajes que genera el protocolo. Otros factores pueden incluir el uso de la memoria y el tamaño de los mensajes.
Diferentes modelos de cálculo pueden definir un "problema de consenso". Algunos modelos pueden tratar con gráficos completamente conectados, mientras que otros pueden tratar con anillos y árboles. En algunos modelos se permite la autenticación de mensajes, mientras que en otros los procesos son completamente anónimos. Los modelos de memoria compartida en los que los procesos se comunican accediendo a objetos en la memoria compartida también son un área importante de investigación.
En la mayoría de los modelos de protocolo de comunicación, los participantes se comunican a través de canales autenticados. Esto significa que los mensajes no son anónimos y los receptores conocen la fuente de cada mensaje que reciben. Algunos modelos asumen una forma de autenticación más fuerte y transferible , donde cada mensaje está firmado por el remitente, de modo que el receptor conoce no sólo la fuente inmediata de cada mensaje, sino también el participante que creó inicialmente el mensaje. Este tipo de autenticación más sólida se logra mediante firmas digitales y, cuando esta forma de autenticación más sólida está disponible, los protocolos pueden tolerar una mayor cantidad de fallas. [2]
Los dos modelos de autenticación diferentes a menudo se denominan modelos de comunicación oral y comunicación escrita . En un modelo de comunicación oral, se conoce la fuente inmediata de información, mientras que en modelos de comunicación escrita más potentes, en cada paso el receptor aprende no sólo la fuente inmediata del mensaje, sino también el historial de comunicación del mensaje. [3]
En los protocolos de consenso de valor único más tradicionales , como Paxos , los nodos cooperantes acuerdan un valor único, como un número entero, que puede ser de tamaño variable para codificar metadatos útiles , como una transacción enviada a una base de datos.
Un caso especial del problema de consenso de un solo valor, llamado consenso binario , restringe la entrada y, por tanto, el dominio de salida, a un solo dígito binario {0,1}. Si bien no son muy útiles por sí mismos, los protocolos de consenso binarios suelen ser útiles como componentes básicos de protocolos de consenso más generales, especialmente para el consenso asincrónico.
En los protocolos de consenso de valores múltiples como Multi-Paxos y Raft , el objetivo es acordar no solo un valor único sino una serie de valores a lo largo del tiempo, formando una historia en crecimiento progresivo. Si bien se puede lograr ingenuamente un consenso de valores múltiples ejecutando múltiples iteraciones sucesivas de un protocolo de consenso de un solo valor, muchas optimizaciones y otras consideraciones, como el soporte de reconfiguración, pueden hacer que los protocolos de consenso de valores múltiples sean más eficientes en la práctica.
Hay dos tipos de fallas que puede sufrir un proceso, una falla por choque o una falla bizantina . Una falla por accidente ocurre cuando un proceso se detiene abruptamente y no se reanuda. Los fracasos bizantinos son fracasos en los que no se impone ninguna condición. Por ejemplo, pueden ocurrir como resultado de acciones maliciosas de un adversario. Un proceso que experimenta una falla bizantina puede enviar datos contradictorios o conflictivos a otros procesos, o puede suspenderse y luego reanudar la actividad después de un largo retraso. De los dos tipos de fracasos, los bizantinos son mucho más perturbadores.
Por tanto, un protocolo de consenso que tolere los fracasos bizantinos debe ser resistente a todos los posibles errores que puedan ocurrir.
Una versión más fuerte del consenso que tolera los fracasos bizantinos se obtiene fortaleciendo la restricción de integridad:
El problema del consenso puede considerarse en el caso de sistemas asíncronos o síncronos. Si bien las comunicaciones del mundo real suelen ser inherentemente asíncronas, es más práctico y a menudo más fácil modelar sistemas síncronos, [4] dado que los sistemas asíncronos implican naturalmente más problemas que los síncronos.
En los sistemas síncronos, se supone que todas las comunicaciones se realizan en rondas . En una ronda, un proceso puede enviar todos los mensajes que necesita y al mismo tiempo recibir todos los mensajes de otros procesos. De esta manera, ningún mensaje de una ronda podrá influir en los mensajes enviados dentro de la misma ronda.
En un sistema distribuido de paso de mensajes totalmente asincrónico, en el que al menos un proceso puede tener una falla , se ha demostrado en el famoso resultado de imposibilidad FLP de 1985 de Fischer, Lynch y Paterson que un algoritmo determinista para lograr el consenso es imposible. [5] Este resultado de imposibilidad se deriva de los peores escenarios de programación, que es poco probable que ocurran en la práctica excepto en situaciones adversas como un atacante inteligente de denegación de servicio en la red. En la mayoría de situaciones normales, la programación de procesos tiene un grado de aleatoriedad natural. [4]
En un modelo asincrónico, algunas formas de fallas pueden manejarse mediante un protocolo de consenso sincrónico. Por ejemplo, la pérdida de un enlace de comunicación puede modelarse como un proceso que ha sufrido un fallo bizantino.
Los algoritmos de consenso aleatorios pueden eludir el resultado de imposibilidad de FLP al lograr seguridad y vitalidad con una probabilidad abrumadora, incluso en los peores escenarios de programación, como un atacante inteligente de denegación de servicio en la red. [6]
Los algoritmos de consenso tradicionalmente suponen que el conjunto de nodos participantes es fijo y dado desde el principio: es decir, que algún proceso de configuración previo (manual o automático) ha permitido que un grupo particular conocido de participantes puedan autenticarse entre sí como miembros del grupo. En ausencia de un grupo cerrado y bien definido con miembros autenticados, un ataque Sybil contra un grupo de consenso abierto puede derrotar incluso un algoritmo de consenso bizantino, simplemente creando suficientes participantes virtuales para superar el umbral de tolerancia a fallas.
Por el contrario, un protocolo de consenso sin permiso permite que cualquier persona en la red se una dinámicamente y participe sin permiso previo, pero en su lugar impone una forma diferente de costo artificial o barrera de entrada para mitigar la amenaza de ataque Sybil . Bitcoin introdujo el primer protocolo de consenso sin permiso que utiliza prueba de trabajo y una función de ajuste de dificultad, en el que los participantes compiten para resolver acertijos hash criptográficos y, probabilísticamente, obtienen el derecho a comprometer bloques y obtener recompensas asociadas en proporción a su esfuerzo computacional invertido. Motivados en parte por el alto costo energético de este enfoque, los protocolos de consenso posteriores sin permiso han propuesto o adoptado otras reglas de participación alternativas para la protección contra ataques de Sybil, como prueba de participación , prueba de espacio y prueba de autoridad .
Tres problemas de acuerdo de interés son los siguientes.
Una colección de procesos, numerados para comunicarse enviándose mensajes entre sí. El proceso debe transmitir un valor a todos los procesos de manera que:
También se le conoce como El problema del general.
Los requisitos formales para un protocolo de consenso pueden incluir:
Para n procesos en un sistema parcialmente sincrónico (el sistema alterna entre períodos buenos y malos de sincronía), cada proceso elige un valor privado. Los procesos se comunican entre sí mediante rondas para determinar un valor público y generar un vector de consenso con los siguientes requisitos: [7]
Se puede demostrar que las variaciones de estos problemas son equivalentes en el sentido de que la solución de un problema en un tipo de modelo puede ser la solución de otro problema en otro tipo de modelo. Por ejemplo, una solución al problema general bizantino débil en un modelo de paso de mensajes autenticados sincrónicos conduce a una solución para la coherencia interactiva débil. [8] Un algoritmo de consistencia interactivo puede resolver el problema del consenso haciendo que cada proceso elija el valor mayoritario en su vector de consenso como su valor de consenso. [9]
Existe un protocolo síncrono anónimo resistente a t que resuelve el problema de los generales bizantinos , [10] [11] si y el caso de los generales bizantinos débiles [8] donde es el número de fallas y el número de procesos.
Para sistemas con procesadores, de los cuales son bizantinos, se ha demostrado que no existe ningún algoritmo que resuelva el problema de consenso en el modelo de mensajes orales . [12] La prueba se construye mostrando primero la imposibilidad para el caso de tres nodos y utilizando este resultado para argumentar sobre las particiones de los procesadores. En el modelo de mensajes escritos existen protocolos que pueden tolerar . [2]
En un sistema totalmente asíncrono no existe una solución de consenso que pueda tolerar uno o más fallos incluso cuando sólo se requiere la propiedad de no trivialidad. [5] Este resultado a veces se denomina prueba de imposibilidad FLP y lleva el nombre de los autores Michael J. Fischer , Nancy Lynch y Mike Paterson , quienes recibieron un premio Dijkstra por este importante trabajo. Se ha verificado mecánicamente que el resultado del FLP se mantiene incluso bajo supuestos de equidad . [13] Sin embargo, FLP no afirma que nunca se pueda alcanzar el consenso: simplemente que, según los supuestos del modelo, ningún algoritmo siempre puede alcanzar el consenso en un tiempo limitado. En la práctica es muy poco probable que esto ocurra.
El algoritmo de consenso Paxos de Leslie Lamport , y sus variantes, como Raft , se utilizan de forma generalizada en sistemas de computación en la nube y distribuidos ampliamente implementados . Estos algoritmos suelen ser sincrónicos, dependen de un líder electo para avanzar y toleran sólo fallas y no fallas bizantinas.
Un ejemplo de un protocolo de consenso binario de tiempo polinomial que tolera fallas bizantinas es el algoritmo Phase King de Garay y Berman. [14] El algoritmo resuelve el consenso en un modelo de paso de mensajes sincrónico con n procesos y hasta f fallas, siempre que n > 4 f . En el algoritmo del rey de fases, hay f + 1 fases, con 2 rondas por fase. Cada proceso realiza un seguimiento de su salida preferida (inicialmente igual al valor de entrada del propio proceso). En la primera ronda de cada fase, cada proceso transmite su propio valor preferido a todos los demás procesos. Luego recibe los valores de todos los procesos y determina qué valor es el valor mayoritario y su recuento. En la segunda ronda de la fase, el proceso cuya identificación coincide con el número de fase actual es designado rey de la fase. El rey transmite el valor mayoritario que observó en la primera ronda y sirve como desempate. Luego, cada proceso actualiza su valor preferido de la siguiente manera. Si el conteo del valor mayoritario del proceso observado en la primera ronda es mayor que n /2 + f , el proceso cambia su preferencia a ese valor mayoritario; de lo contrario, utiliza el valor del rey de fase. Al final de las fases f + 1, los procesos generan sus valores preferidos.
Google ha implementado una biblioteca de servicios de bloqueo distribuido llamada Chubby . [15] Chubby mantiene la información de bloqueo en pequeños archivos que se almacenan en una base de datos replicada para lograr una alta disponibilidad ante fallas. La base de datos se implementa sobre una capa de registro tolerante a fallas que se basa en el algoritmo de consenso de Paxos . En este esquema, los clientes Chubby se comunican con el maestro de Paxos para acceder/actualizar el registro replicado; es decir, leer/escribir en los archivos. [dieciséis]
Muchos juegos de estrategia en tiempo real en línea peer-to-peer utilizan un protocolo de bloqueo modificado como protocolo de consenso para gestionar el estado del juego entre los jugadores. Cada acción del juego da como resultado una transmisión delta del estado del juego a todos los demás jugadores junto con un hash del estado total del juego. Cada jugador valida el cambio aplicando el delta a su propio estado del juego y comparando los hashes del estado del juego. Si los hashes no coinciden, se emite una votación y aquellos jugadores cuyo estado de juego es minoría son desconectados y eliminados del juego (lo que se conoce como desincronización).
Otro enfoque bien conocido son los llamados algoritmos de tipo MSR, que se han utilizado ampliamente desde la informática hasta la teoría del control. [17] [18] [19]
Bitcoin utiliza prueba de trabajo , una función de ajuste de dificultad y una función de reorganización para lograr un consenso sin permiso en su red abierta de igual a igual . Para ampliar la cadena de bloques o el libro mayor distribuido de Bitcoin , los mineros intentan resolver un rompecabezas criptográfico, donde la probabilidad de encontrar una solución es proporcional al esfuerzo computacional invertido en hashes por segundo. Al nodo que primero resuelve dicho rompecabezas se le agrega la versión propuesta del siguiente bloque de transacciones al libro mayor y finalmente es aceptada por todos los demás nodos. Como cualquier nodo de la red puede intentar resolver el problema de prueba de trabajo, un ataque Sybil es, en principio, inviable a menos que el atacante tenga más del 50% de los recursos computacionales de la red.
Otras criptomonedas (por ejemplo, Ethereum , NEO, STRATIS, ...) utilizan prueba de participación , en la que los nodos compiten para agregar bloques y obtener recompensas asociadas en proporción a la participación , o la criptomoneda existente asignada y bloqueada o apostada durante algún período de tiempo. Una ventaja de un sistema de 'prueba de participación' sobre un sistema de 'prueba de trabajo' es el alto consumo de energía que demanda este último. Como ejemplo, se estima que la minería de Bitcoin (2018) consume fuentes de energía no renovables en una cantidad similar a las naciones enteras de la República Checa o Jordania, mientras que el consumo total de energía de Ethereum, la red de prueba de participación más grande, es un poco menos la de 205 hogares estadounidenses promedio. [29] [30] [31]
Algunas criptomonedas, como Ripple, utilizan un sistema de nodos de validación para validar el libro mayor. Este sistema utilizado por Ripple, llamado Ripple Protocol Consensus Algorithm (RPCA), funciona en rondas:
Otras reglas de participación utilizadas en protocolos de consenso sin permiso para imponer barreras de entrada y resistir ataques de sybil incluyen prueba de autoridad , prueba de espacio , prueba de quemado o prueba de tiempo transcurrido.
En contraste con las reglas de participación sin permiso anteriores, todas las cuales recompensan a los participantes en proporción a la cantidad de inversión en alguna acción o recurso, los protocolos de prueba de personalidad tienen como objetivo darle a cada participante humano real exactamente una unidad de poder de voto en un consenso sin permiso, independientemente de la inversión económica. . [33] [34] Los enfoques propuestos para lograr una distribución por persona del poder de consenso para la prueba de la personalidad incluyen partidos con seudónimos físicos, [35] redes sociales, [36] identidades seudonimizadas emitidas por el gobierno, [37] y datos biométricos. [38]
Para resolver el problema del consenso en un sistema de memoria compartida, se deben introducir objetos concurrentes. Un objeto concurrente, u objeto compartido, es una estructura de datos que ayuda a los procesos concurrentes a comunicarse para llegar a un acuerdo. Las implementaciones tradicionales que utilizan secciones críticas corren el riesgo de fallar si algún proceso muere dentro de la sección crítica o permanece inactivo durante un tiempo intolerablemente largo. Los investigadores definieron la libertad de espera como la garantía de que el algoritmo se completa en un número finito de pasos.
El número de consenso de un objeto concurrente se define como el número máximo de procesos en el sistema que pueden llegar a un consenso mediante el objeto dado en una implementación sin espera. [39] Los objetos con un número de consenso de pueden implementar cualquier objeto con un número de consenso de o inferior, pero no pueden implementar ningún objeto con un número de consenso mayor. Los números de consenso forman lo que se llama la jerarquía de objetos de sincronización de Herlihy . [40]
Según la jerarquía, los registros de lectura/escritura no pueden resolver el consenso ni siquiera en un sistema de dos procesos. Las estructuras de datos como pilas y colas solo pueden resolver el consenso entre dos procesos. Sin embargo, algunos objetos concurrentes son universales (anotados en la tabla con ), lo que significa que pueden resolver el consenso entre cualquier número de procesos y pueden simular cualquier otro objeto a través de una secuencia de operaciones. [39]
{{cite book}}
: |journal=
ignorado ( ayuda )