Consenso (informática)

Concepto en informática

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 procesos de coordinación 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 del estado , control de vehículos aéreos no tripulados (y múltiples robots/agentes en general), equilibrio de carga , blockchain y otras.

Descripción del problema

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] ^[1]

Terminación

Al final, cada proceso correcto decide algún valor.

Integridad

Si todos los procesos correctos propusieron el mismo valor , entonces cualquier proceso correcto debe decidir . ${\displaystyle v}$ ${\displaystyle v}$

Acuerdo

Todo proceso correcto debe coincidir en el mismo valor.

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 como máximo t fallan 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.

Modelos de computacion

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.

Canales de comunicación con autenticación directa o transferible

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 fuertes, 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]

Entradas y salidas del consenso

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 el consenso de valores múltiples se puede lograr de manera ingenua 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.

Crash y fracasos bizantinos

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 lo 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:

Integridad

Si decide un proceso correcto , entonces debe haber sido propuesto por algún proceso correcto. ${\displaystyle v}$ ${\displaystyle v}$

Sistemas asíncronos y síncronos.

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.

El resultado de imposibilidad del FLP para el consenso determinista asincrónico

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]

Consenso con permiso versus sin permiso

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

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 .

Problemas de equivalencia de acuerdos

Tres problemas de acuerdo de interés son los siguientes.

Terminar la transmisión confiable

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: ${\displaystyle n}$ ${\displaystyle 0}$ ${\displaystyle n-1,}$ ${\displaystyle 0}$ ${\displaystyle v}$

1. Si el proceso es correcto, entonces cada proceso correcto recibe ${\displaystyle 0}$ ${\displaystyle v}$
2. para dos procesos correctos cualesquiera, cada proceso recibe el mismo valor.

También se le conoce como El problema del general.

Consenso

Los requisitos formales para un protocolo de consenso pueden incluir:

• Acuerdo : Todos los procesos correctos deben acordar el mismo valor.
• Validez débil : para cada proceso correcto, su salida debe ser la entrada de algún proceso correcto.
• Validez fuerte : si todos los procesos correctos reciben el mismo valor de entrada, todos deben generar ese valor.
• Terminación : todos los procesos deben eventualmente decidir sobre un valor de salida.

Consistencia interactiva débil

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]

1. si un proceso correcto envía , entonces todos los procesos correctos reciben o nada (propiedad de integridad) ${\displaystyle v}$ ${\displaystyle v}$
2. todos los mensajes enviados en una ronda por un proceso correcto son recibidos en la misma ronda por todos los procesos correctos (propiedad de coherencia).

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]

Resultados de solubilidad para algunos problemas de acuerdo.

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. ${\displaystyle {\tfrac {t}{n}}<{\tfrac {1}{3}}}$ ${\displaystyle t}$ ${\displaystyle n}$

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] ${\displaystyle n}$ ${\displaystyle f}$ ${\displaystyle n\leq 3f}$ ${\displaystyle n=3}$ ${\displaystyle n=f+1}$

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.

Algunos protocolos de consenso

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

Protocolos de consenso sin permiso

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:

Paso 1: cada servidor compila una lista de transacciones candidatas válidas;

Paso 2: cada servidor fusiona todos los candidatos provenientes de su Lista de Nodos Únicos (UNL) y vota sobre su veracidad;

Paso 3: las transacciones que superan el umbral mínimo pasan a la siguiente ronda;

Paso 4: la ronda final requiere un 80% de acuerdo. ^[32]

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]

Número de consenso

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] ${\displaystyle n}$ ${\displaystyle n}$

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] ${\displaystyle \infty }$

Ver también

• Consenso uniforme
• Acuerdo bizantino cuántico
• Tolerancia a fallas bizantinas

Referencias

1. George Coulouris; Jean Dollimore ; Tim Kindberg (2001), Sistemas distribuidos: conceptos y diseño (3ª ed.), Addison-Wesley, p. 452, ISBN 978-0201-61918-8
2. Dolev, D.; Fuerte, Recursos Humanos (1983). "Algoritmos autenticados para el acuerdo bizantino". Revista SIAM de Computación . 12 (4): 656–666. doi :10.1137/0212045.
3. Gong, Li; Lincoln, Patricio; Rushby, John (1995). "Acuerdo bizantino con autenticación". Computación confiable para aplicaciones críticas . 10 .
4. Aguilera, MK (2010). "Tropezando con la investigación del consenso: malentendidos y problemas". Replicación . Apuntes de conferencias sobre informática. vol. 5959, págs. 59–72. doi :10.1007/978-3-642-11294-2_4. ISBN 978-3-642-11293-5.
5. Fischer, MJ ; Lynch, NA ; Paterson, MS (1985). "Imposibilidad de consenso distribuido con un proceso defectuoso" (PDF) . Revista de la ACM . 32 (2): 374–382. doi :10.1145/3149.214121. S2CID  207660233.
6. Aspnes, James (mayo de 1993). "Consenso aleatorio eficiente en tiempo y espacio". Revista de algoritmos . 14 (3): 414–431. doi :10.1006/jagm.1993.1022.
7. Milosevic, Zarko; Martín Hutle; André Schiper (2009). "Unificación de algoritmos de consenso bizantinos con consistencia interactiva débil" . Principios de los sistemas distribuidos . Apuntes de conferencias sobre informática. vol. 5293, págs. 300–314. CiteSeerX 10.1.1.180.4229 . doi :10.1007/978-3-642-10877-8_24. ISBN  978-3-642-10876-1. {{cite book}}: |journal=ignorado ( ayuda )
8. Lamport, L. (1983). "El problema de los generales bizantinos débiles". Revista de la ACM . 30 (3): 668. doi : 10.1145/2402.322398 . S2CID  1574706.
9. Fischer, Michael J. "El problema del consenso en sistemas distribuidos no confiables (una breve encuesta)" (PDF) . Archivado desde el original (PDF) el 22 de abril de 2014 . Consultado el 21 de abril de 2014 .
10. Lamport, L .; Shostak, R.; Pease, M. (1982). "El problema de los generales bizantinos" (PDF) . Transacciones ACM sobre lenguajes y sistemas de programación . 4 (3): 382–401. CiteSeerX 10.1.1.64.2312 . doi :10.1145/357172.357176. S2CID  55899582. 
11. Lamport, Leslie; Marshall Pease; Robert Shostak (abril de 1980). "Llegar a un acuerdo en presencia de fallas" (PDF) . Revista de la ACM . 27 (2): 228–234. CiteSeerX 10.1.1.68.4044 . doi :10.1145/322186.322188. S2CID  6429068 . Consultado el 25 de julio de 2007 . 
12. Attiya, Hagit (2004). Computación distribuida (2ª ed.). Wiley. págs. 101-103. ISBN 978-0-471-45324-6.
13. Bisping, Benjamín; et al. (2016), "Verificación mecánica de una prueba constructiva para FLP", en Blanchette, Jasmin Christian; Merz, Stephan (eds.), Demostración interactiva de teoremas , Apuntes de conferencias sobre informática, vol. 9807, Springer International Publishing, págs. 107–122, doi :10.1007/978-3-319-43144-4_7, ISBN 978-3-319-43144-4
14. Berman, Piotr; Garay, Juan A. (1993). "Votos de cierre: consenso distribuido resistente a n/4 en t + 1 rondas". Teoría de los Sistemas Computacionales . 2. 26 : 3–19. doi :10.1007/BF01187072. S2CID  6102847.
15. Madrigueras, M. (2006). El servicio Chubby Lock para sistemas distribuidos débilmente acoplados (PDF) . Actas del Séptimo Simposio sobre diseño e implementación de sistemas operativos. Asociación USENIX Berkeley, CA, EE. UU. págs. 335–350.
16. Tushar, C.; Griesemer, R.; Redstone, J. (2007). Paxos Made Live: una perspectiva de ingeniería (PDF) . Actas del vigésimo sexto simposio anual de ACM sobre principios de informática distribuida . Portland, Oregon, EE.UU.: ACM Press Nueva York, NY, EE.UU. págs. 398–407. doi :10.1145/1281100.1281103. Archivado desde el original (PDF) el 12 de diciembre de 2014 . Consultado el 6 de febrero de 2008 .
17. LeBlanc, Heath J. (abril de 2013). "Consenso asintótico resiliente en redes robustas". Revista IEEE sobre áreas seleccionadas de las comunicaciones . 31 (4): 766–781. CiteSeerX 10.1.1.310.5354 . doi :10.1109/JSAC.2013.130413. S2CID  11287513. 
18. Dibaji, SM (mayo de 2015). "Consenso de sistemas multiagente de segundo orden en presencia de fallas localmente acotadas". Cartas de sistemas y control . 79 : 23–29. doi :10.1016/j.sysconle.2015.02.005.
19. Dibaji, SM (julio de 2017). "Consenso resiliente de redes de agentes de segundo orden: reglas de actualización asincrónica con retrasos". Automática . 81 : 123-132. arXiv : 1701.03430 . Código Bib : 2017arXiv170103430M. doi :10.1016/j.automatica.2017.03.008. S2CID  7467466.
20. Ben-Or, Michael (1983). "Otra ventaja de la libre elección (resumen ampliado): Protocolos de acuerdo completamente asincrónicos". Actas del segundo simposio anual de ACM sobre principios de informática distribuida . págs. 27–30. doi : 10.1145/800221.806707 . S2CID  38215511.
21. Dolev, Danny; Pescador, Michael J.; cazador de aves, Rob; Lynch, Nancy; Fuerte, H. Raymond (1982). "Un algoritmo eficiente para el acuerdo bizantino sin autenticación". Información y Control . 52 (3): 257–274. doi : 10.1016/S0019-9958(82)90776-8 .
22. Feldman, Pesech; Micali, Sylvio (1997). "Un protocolo probabilístico óptimo para el acuerdo bizantino sincrónico". Revista SIAM de Computación . 26 (4): 873–933. doi :10.1137/S0097539790187084.
23. Katz, Jonathan; Koo, Chiu-Yuen (2006). "Sobre los protocolos de ronda constante esperados para el acuerdo bizantino" . CRIPTO 2006. doi : 10.1007/11818175_27 .
24. Castro, Miguel; Liskov, Bárbara (1999). "Tolerancia práctica a fallas bizantinas" (PDF) . Actas del tercer simposio sobre diseño e implementación de sistemas operativos, Nueva Orleans, EE. UU., febrero de 1999 .
25. Molinero, Andrés; Xia, Yu; Croman, Kyle; Shi, Elaine ; Canción, amanecer (octubre de 2016). "El tejón de miel de los protocolos BFT" (PDF) . CCS '16: Actas de la Conferencia ACM SIGSAC de 2016 sobre seguridad informática y de las comunicaciones . págs. 31–42. doi :10.1145/2976749.2978399.
26. Abraham, Ittai; Devadas, Srinivas; Dolev, Danny; Nayak, Kartik; Ren, Ling (11 de septiembre de 2017). "Consenso bizantino síncrono eficiente" (PDF) . Archivo ePrint de criptología . Documento 2017/307.
27. Micali, Sylvio (19 de marzo de 2018). "El acuerdo bizantino se volvió trivial" (PDF) . Cambridge, MA: CSAIL, MIT.
28. Chen, Jing; Micali, Silvio (2016). "ALGORANDO". arXiv : 1607.01341v9 [cs.CR].
29. Irfan, Umair (18 de junio de 2019). "Bitcoin consume energía. ¿De dónde viene toda esa electricidad?". Vox .
30. "La fusión: implicaciones sobre el consumo de electricidad y la huella de carbono de la red Ethereum". 7 de septiembre de 2022.
31. "Consumo de electricidad per cápita en todo el mundo en 2022, por país seleccionado".
32. Schwartz, David; Jóvenes, Noé; Britto, Arturo (2014). "El algoritmo de consenso del protocolo Ripple" (PDF) . Ripple Labs (borrador).
33. María Borge; Eleftherios Kokoris-Kogias; Philipp Jovanovic; Linus Gasser; Nicolás Gailly; Bryan Ford (29 de abril de 2017). Prueba de personalidad: redemocratización de las criptomonedas sin permiso. Seguridad y privacidad de IEEE en Blockchain (IEEE S&B). doi :10.1109/EuroSPW.2017.46.
34. Divya Siddarth; Serguéi Ivliev; Santiago Siri; Paula Berman (13 de octubre de 2020). "¿Quién vigila a los vigilantes? Una revisión de enfoques subjetivos para la resistencia a las sibilas en los protocolos de prueba de personalidad". arXiv : 2008.05300 [cs.CR].
35. Ford, Bryan; Strauss, Jacob (abril de 2008). Una base fuera de línea para seudónimos responsables en línea . 1er Taller sobre Sistemas de Redes Sociales - SocialNets '08. págs. 31–36. doi :10.1145/1435497.1435503. ISBN 978-1-60558-124-8.
36. Gal Shahaf; Ehud Shapiro; Nimrod Talmon (octubre de 2020). Identificadores personales genuinos y garantías mutuas para el crecimiento comunitario resiliente de Sybil. Congreso Internacional de Informática Social. arXiv : 1904.09630 . doi :10.1007/978-3-030-60975-7_24.
37. Deepak Maram; Harjasleen Malvai; Fan Zhang; Nerla Jean-Louis; Alejandro Frolov; Tyler Kell; Tyrone Lobban; Cristina Moy; Ari Juels; Andrew Miller (28 de septiembre de 2020). "CanDID: Identidad descentralizada que se puede hacer con compatibilidad heredada, resistencia a Sybil y responsabilidad" (PDF) .
38. Mohammad-Javad Hajialikhani; Mohammad-Mahdi Jahanara (20 de junio de 2018). "UniqueID: prueba descentralizada de ser humano único". arXiv : 1806.07583 [cs.CR].
39. Herlihy, Maurice (enero de 1991). "Sincronización sin esperas" (PDF) . Transacciones ACM sobre lenguajes y sistemas de programación . 11 (1): 124-149. doi :10.1145/114005.102808. S2CID  2181446 . Consultado el 19 de diciembre de 2011 .
40. Imbs, Damián; Raynal, Michel (25 de julio de 2010). "El poder multiplicativo de los números de consenso" (PDF) . Actas del 29º simposio ACM SIGACT-SIGOPS sobre principios de informática distribuida . Asociación para Maquinaria de Computación. págs. 26–35. doi :10.1145/1835698.1835705. ISBN 978-1-60558-888-9. S2CID  3179361 . Consultado el 22 de abril de 2021 .
41. Fich, fe; Hendler, Danny; Shavit, Nir (25 de julio de 2004). "Sobre la debilidad inherente de las primitivas de sincronización condicional". Actas del vigésimo tercer simposio anual de ACM sobre principios de informática distribuida . Asociación para Maquinaria de Computación. págs. 80–87. CiteSeerX 10.1.1.96.9340 . doi :10.1145/1011767.1011780. ISBN  1-58113-802-4. S2CID  9313205.

Otras lecturas

• Herlihy, M.; Shavit, N. (1999). "La estructura topológica de la computabilidad asincrónica". Revista de la ACM . 46 (6): 858. CiteSeerX  10.1.1.78.1455 . doi :10.1145/331524.331529. S2CID  5797174.
• Saks, M.; Zaharoglou, F. (2000). "El acuerdo k-Set sin espera es imposible: la topología del conocimiento público". Revista SIAM de Computación . 29 (5): 1449-1483. doi :10.1137/S0097539796307698.
• Bashir, Imran. "Consenso de Blockchain". Consenso de Blockchain: una introducción a los protocolos de consenso clásicos, de blockchain y cuánticos . ISBN 978-1-4842-8178-9 Apress, Berkeley, CA, 2022. doi :10.1007/978-1-4842-8179-6