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 la coordinación de procesos para alcanzar 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 confirmar en una base de datos 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 , cadena de bloques y otras.

Descripción del problema

El problema del consenso requiere que varios procesos (o agentes) lleguen a un acuerdo sobre un único valor de datos. Algunos de los procesos (agentes) pueden fallar o no ser confiables de alguna otra manera, por lo que los protocolos de consenso deben ser tolerantes a fallas o resilientes. Los procesos deben proponer sus valores candidatos, comunicarse entre sí y acordar un único valor 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 cada proceso recibe un voto). Sin embargo, uno o más procesos defectuosos pueden distorsionar el resultado resultante de tal manera que no se alcance el consenso o que se alcance incorrectamente.

Los protocolos que resuelven problemas de consenso están diseñados para tratar con un número limitado de procesos defectuosos . Estos protocolos deben satisfacer varios requisitos para ser útiles. Por ejemplo, un protocolo trivial podría hacer que todos los procesos generen un valor binario de salida 1. Esto no es útil; por lo tanto, el requisito se modifica de modo que la producción debe depender de la entrada. 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 puede decidir sobre un valor de salida solo 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 fallos de detención debe satisfacer las siguientes propiedades. ^[1]

Terminación

Al final, todo 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 aplicación, pueden ser adecuadas 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 fuera igual a un valor que proponía 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 rendimiento de los protocolos de consenso, dos factores de interés son el tiempo de ejecución y la complejidad de los mensajes . El tiempo de ejecución se expresa en notación Big O en la cantidad de rondas de intercambio de mensajes como una función de algunos parámetros de entrada (normalmente la cantidad de procesos o el tamaño del dominio de entrada). La complejidad de los mensajes 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 computación

Los distintos modelos de computación pueden definir un "problema de consenso". Algunos modelos pueden tratar con grafos 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 protocolos 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 suponen una forma de autenticación más fuerte y transferible , en la que cada mensaje está firmado por el remitente, de modo que el receptor no sólo conoce la fuente inmediata de cada mensaje, sino también el participante que creó inicialmente el mensaje. Este tipo de autenticación más fuerte se logra mediante firmas digitales y, cuando está disponible, los protocolos pueden tolerar una mayor cantidad de fallas. ^[2]

Los dos modelos de autenticación diferentes se denominan a menudo modelos de comunicación oral y modelos de comunicación escrita . En un modelo de comunicación oral, se conoce la fuente inmediata de información, mientras que en los modelos de comunicación escrita más sólidos, en cada paso el receptor no solo conoce 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 valor único, llamado consenso binario , restringe el dominio de entrada y, por lo tanto, de salida, a un solo dígito binario {0,1}. Si bien no son muy útiles por sí mismos, los protocolos de consenso binario suelen ser útiles como bloques de construcción en protocolos de consenso más generales, especialmente para el consenso asincrónico.

En los protocolos de consenso de múltiples valores , 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 un historial que crece progresivamente. Si bien el consenso de múltiples valores se puede lograr de manera simple ejecutando varias iteraciones de un protocolo de consenso de un solo valor en sucesión, muchas optimizaciones y otras consideraciones, como el soporte de reconfiguración, pueden hacer que los protocolos de consenso de múltiples valores sean más eficientes en la práctica.

Crash y fracasos bizantinos

Hay dos tipos de fallos que puede sufrir un proceso: un fallo por caída o un fallo bizantino . Un fallo por caída ocurre cuando un proceso se detiene abruptamente y no se reanuda. Los fallos bizantinos son fallos en los que no se imponen condiciones en absoluto. Por ejemplo, pueden ocurrir como resultado de las acciones maliciosas de un adversario. Un proceso que experimenta un fallo bizantino puede enviar datos contradictorios o conflictivos a otros procesos, o puede suspenderse y luego reanudar la actividad después de una demora prolongada. De los dos tipos de fallos, los fallos bizantinos son mucho más disruptivos.

Por lo tanto, un protocolo de consenso que tolere fallos bizantinos debe ser resiliente a cualquier posible error que pueda ocurrir.

Una versión más fuerte del consenso que tolera los fracasos bizantinos se da fortaleciendo la restricción de integridad:

Integridad

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

Sistemas asincrónicos y sincrónicos

El problema del consenso puede considerarse en el caso de sistemas asincrónicos o sincrónicos. Si bien las comunicaciones del mundo real suelen ser inherentemente asincrónicas, resulta más práctico y a menudo más fácil modelar sistemas sincrónicos, ^[4] dado que los sistemas asincrónicos naturalmente implican más problemas que los sincrónicos.

En los sistemas sincrónicos, 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 puede influir en los mensajes enviados dentro de la misma ronda.

Resultado de imposibilidad de 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 por caída , 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 escenarios de programación del peor caso, 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 las situaciones normales, la programación de procesos tiene un grado de aleatoriedad natural. ^[4]

En un modelo asincrónico, algunas formas de fallas pueden ser manejadas por un protocolo de consenso sincrónico. Por ejemplo, la pérdida de un enlace de comunicación puede ser modelada como un proceso que ha sufrido una falla bizantina.

Los algoritmos de consenso aleatorio pueden eludir el resultado de imposibilidad de FLP al lograr seguridad y actividad 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 consenso 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 autorizado a un grupo particular conocido de participantes que pueden 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 a un algoritmo de consenso bizantino, simplemente creando suficientes participantes virtuales para superar el umbral de tolerancia a fallas.

Un protocolo de consenso sin permiso , por el contrario, permite que cualquiera 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 usando prueba de trabajo y una función de ajuste de dificultad, en el que los participantes compiten para resolver acertijos criptográficos y ganan probabilísticamente el derecho a comprometer bloques y ganar 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 sin permiso posteriores han propuesto o adoptado otras reglas de participación alternativas para la protección contra ataques Sybil, como prueba de participación , prueba de espacio y prueba de autoridad .

Problemas de equivalencia de acuerdos

A continuación se presentan tres problemas de acuerdo de interés:

Terminación de la transmisión confiable

Una colección de procesos, numerados de a a comunicarse mediante el envío de 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, cada proceso recibe el mismo valor.

También se conoce como el problema del general.

Consenso

Los requisitos formales para un protocolo de consenso pueden incluir:

• Acuerdo : Todos los procesos correctos deben coincidir en 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, entonces todos deben generar ese valor como salida.
• Terminación : Todos los procesos deben decidir eventualmente 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 uno 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 consistencia).

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 autenticado sincrónico conduce a una solución para la consistencia interactiva débil. ^[8] Un algoritmo de consistencia interactiva puede resolver el problema de 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 t-resiliente 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 es el número de procesos. ${\displaystyle {\tfrac {t}{n}}<{\tfrac {1}{3}}}$ ${\displaystyle t}$ ${\displaystyle n}$

Para los sistemas con procesadores, de los cuales son bizantinos, se ha demostrado que no existe ningún algoritmo que resuelva el problema de consenso para en el modelo de mensajes orales . ^[12] La prueba se construye mostrando primero la imposibilidad para el caso de tres nodos y usando este resultado para argumentar sobre particiones de procesadores. En el modelo de mensajes escritos hay protocolos que pueden tolerar . ^[2] ${\displaystyle n}$ ${\displaystyle f}$ ${\displaystyle n\leq 3f}$ ${\displaystyle n=3}$ ${\displaystyle n=f+1}$

En un sistema completamente asincrónico no existe una solución de consenso que pueda tolerar uno o más fallos de bloqueo incluso cuando solo se requiere la propiedad de no trivialidad. ^[5] Este resultado a veces se denomina prueba de imposibilidad FLP en honor a los autores Michael J. Fischer , Nancy Lynch y Mike Paterson , quienes recibieron un premio Dijkstra por este importante trabajo. El resultado FLP se ha verificado mecánicamente para que se mantenga incluso bajo supuestos de imparcialidad . ^[13] Sin embargo, FLP no afirma que nunca se pueda alcanzar el consenso: simplemente que bajo los supuestos del modelo, ningún algoritmo siempre puede alcanzar el consenso en un tiempo acotado. En la práctica, es muy poco probable que 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 informáticos distribuidos y en la nube ampliamente implementados . Estos algoritmos suelen ser sincrónicos, dependen de un líder elegido para avanzar y solo toleran fallos 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 Phase King, 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 cuyo id coincide con el número de fase actual se designa como el 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 recuento del valor mayoritario observado por el proceso 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 la fase. Al final de f + 1 fases, los procesos muestran sus valores preferidos.

Google ha implementado una biblioteca de servicios de bloqueo distribuidos 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 en caso de 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 de Chubby se comunican con el maestro de Paxos para acceder/actualizar el registro replicado; es decir, leer/escribir en los archivos. ^[16]

Muchos juegos de estrategia en tiempo real en línea entre pares utilizan un protocolo Lockstep modificado como protocolo de consenso para gestionar el estado del juego entre los jugadores de un juego. Cada acción del juego da como resultado una transmisión delta del estado del juego a todos los demás jugadores del juego 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 realiza una votación y aquellos jugadores cuyo estado del juego está en minoría se desconectan y se eliminan 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 en la ciencia informática y la teoría de control. ^{[17] [18] [19]}

Protocolos de consenso sin permisos

Bitcoin utiliza una prueba de trabajo , una función de ajuste de dificultad y una función de reorganización para lograr un consenso sin permisos en su red abierta entre pares . Para extender 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 gastado en hashes por segundo. El nodo que primero resuelve dicho rompecabezas tiene su versión propuesta del siguiente bloque de transacciones agregada al libro mayor y eventualmente aceptada por todos los demás nodos. Como cualquier nodo en la red puede intentar resolver el problema de la prueba de trabajo, un ataque Sybil es inviable en principio 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 ganar recompensas asociadas en proporción a la participación , o criptomonedas existentes asignadas y bloqueadas o apostadas por un período de tiempo determinado. 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 bitcoins (2018) consume fuentes de energía no renovables en una cantidad similar a la de todas las naciones 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 apenas inferior al de 205 hogares estadounidenses promedio. ^{[29] [30] [31]}

Algunas criptomonedas, como Ripple, utilizan un sistema de nodos de validación para validar el libro de contabilidad. 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 acuerdo del 80%. ^[32]

Otras reglas de participación utilizadas en protocolos de consenso sin permiso para imponer barreras de entrada y resistir ataques de sibila incluyen prueba de autoridad , prueba de espacio , prueba de quema o prueba de tiempo transcurrido.

En contraste con las reglas de participación sin permiso mencionadas anteriormente, 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 apuntan a dar a cada participante humano real exactamente una unidad de poder de voto en el consenso sin permiso, independientemente de la inversión económica. ^{[33] [34]} Los enfoques propuestos para lograr una distribución de poder de consenso de uno por persona para la prueba de personalidad incluyen partidos con seudónimos físicos, ^[35] redes sociales, ^[36] identidades emitidas por el gobierno seudónimas, ^[37] y biometría. ^[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 se enfrentan al riesgo de bloquearse 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 complete 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 alcanzar el consenso por 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 menor, pero no pueden implementar ningún objeto con un número de consenso mayor. Los números de consenso forman lo que se denomina 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 }$

Véase también

• Consenso uniforme
• Acuerdo cuántico bizantino
• Falla bizantina

Referencias

1. George Coulouris; Jean Dollimore ; Tim Kindberg (2001), Sistemas distribuidos: conceptos y diseño (3.ª ed.), Addison-Wesley, pág. 452, ISBN 978-0201-61918-8
2. Dolev, D.; Strong, HR (1983). "Algoritmos autenticados para el acuerdo bizantino". Revista SIAM de Computación . 12 (4): 656–666. doi :10.1137/0212045.
3. Gong, Li; Lincoln, Patrick; Rushby, John (1995). "Acuerdo bizantino con autenticación". Computación confiable para aplicaciones críticas . 10 . Archivado desde el original el 2020-01-05 . Consultado el 2019-05-28 .
4. Aguilera, MK (2010). "Tropezando con la investigación de consenso: malentendidos y problemas". Replication . Lecture Notes in Computer Science. 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) . Journal of the ACM . 32 (2): 374–382. doi :10.1145/3149.214121. S2CID  207660233. Archivado (PDF) desde el original el 2023-01-30 . Consultado el 2017-11-13 .
6. Aspnes, James (mayo de 1993). "Consenso aleatorio eficiente en tiempo y espacio". Journal of Algorithms . 14 (3): 414–431. doi :10.1006/jagm.1993.1022. Archivado desde el original el 16 de febrero de 2023 . Consultado el 28 de octubre de 2020 .
7. Milosevic, Zarko; Martin Hutle; Andre Schiper (2009). "Unificación de algoritmos de consenso bizantino con consistencia interactiva débil" . Principles of Distributed Systems . Lecture Notes in Computer Science. 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 reseña)" (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) . ACM Transactions on Programming Languages ​​and Systems . 4 (3): 382–401. CiteSeerX 10.1.1.64.2312 . doi :10.1145/357172.357176. S2CID  55899582. Archivado (PDF) desde el original el 2017-02-07 . Consultado el 2015-08-29 . 
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. Archivado (PDF) desde el original el 28 de enero de 2007 . 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, Benjamin; 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 , Lecture Notes in Computer Science, 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 sistemas informáticos . 2. 26 : 3–19. doi :10.1007/BF01187072. S2CID  6102847.
15. Burrows, M. (2006). El servicio de bloqueo Chubby para sistemas distribuidos de acoplamiento flexible (PDF) . Actas del 7.º Simposio sobre diseño e implementación de sistemas operativos. USENIX Association Berkeley, CA, EE. UU., págs. 335–350. Archivado (PDF) desde el original el 14 de diciembre de 2009. Consultado el 28 de octubre de 2014 .
16. Tushar, C.; Griesemer, R.; Redstone, J. (2007). Paxos Made Live – An Engineering Perspective (PDF) . Actas del vigésimo sexto simposio anual de la ACM sobre principios de computación distribuida . Portland, Oregón, EE. UU.: ACM Press Nueva York, NY, EE. UU. pp. 398–407. doi :10.1145/1281100.1281103. Archivado desde el original (PDF) el 2014-12-12 . Consultado el 2008-02-06 .
17. LeBlanc, Heath J. (abril de 2013). "Consenso asintótico resiliente en redes robustas". Revista IEEE sobre áreas seleccionadas en 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 delimitadas". Systems & Control Letters . 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ónicas con retrasos". Automatica . 81 : 123–132. arXiv : 1701.03430 . Bibcode :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 la ACM sobre Principios de computación distribuida . págs. 27–30. doi : 10.1145/800221.806707 . S2CID  38215511.
21. Dolev, Danny; Fisher, Michael J.; Fowler, Rob; Lynch, Nancy; Strong, 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 . CRYPTO 2006. doi : 10.1007/11818175_27 .
24. Castro, Miguel; Liskov, Barbara (1999). "Practical Byzantine Fault Tolerance" (PDF) . Actas del Tercer Simposio sobre Diseño e Implementación de Sistemas Operativos, Nueva Orleans, EE. UU., febrero de 1999. Archivado (PDF) desde el original el 4 de marzo de 2018. Consultado el 28 de mayo de 2019 .
25. Miller, Andrew; Xia, Yu; Croman, Kyle; Shi, Elaine ; Song, Dawn (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. Archivado (PDF) desde el original el 2023-06-03 . Consultado el 2023-07-04 .
26. Abraham, Ittai; Devadas, Srinivas; Dolev, Danny; Nayak, Kartik; Ren, Ling (11 de septiembre de 2017). "Consenso bizantino sincrónico eficiente" (PDF) . Archivo de ePrint de criptología . Artículo 2017/307. Archivado (PDF) del original el 4 de julio de 2023 . Consultado el 4 de julio de 2023 .
27. Micali, Sylvio (19 de marzo de 2018). "Byzantine agreement made trivial" (PDF) . Cambridge, MA: CSAIL, MIT. Archivado (PDF) del original el 7 de diciembre de 2022. Consultado el 28 de mayo de 2019 .
28. Chen, Jing; Micali, Silvio (2016). "ALGORANDO". arXiv : 1607.01341v9 [cs.CR].
29. Irfan, Umair (18 de junio de 2019). "Bitcoin es un devorador de energía. ¿De dónde viene toda esa electricidad?". Vox . Archivado desde el original el 16 de febrero de 2023. Consultado el 28 de agosto de 2019 .
30. "La fusión: implicaciones en el consumo de electricidad y la huella de carbono de la red Ethereum". 7 de septiembre de 2022. Archivado desde el original el 5 de septiembre de 2023. Consultado el 5 de septiembre de 2023 .
31. "Consumo de electricidad per cápita en todo el mundo en 2022, por país seleccionado". Archivado desde el original el 5 de septiembre de 2023. Consultado el 5 de septiembre de 2023 .
32. Schwartz, David; Youngs, Noah; Britto, Arthur (2014). "El algoritmo de consenso del protocolo Ripple" (PDF) . Ripple Labs (borrador). Archivado (PDF) desde el original el 29 de agosto de 2017. Consultado el 3 de julio de 2023 .
33. Maria Borge; Eleftherios Kokoris-Kogias; Philipp Jovanovic; Linus Gasser; Nicolas Gailly; Bryan Ford (29 de abril de 2017). Proof-of-Personhood: Redemocratizing Permissionless Cryptocurrencies (Prueba de personalidad: redemocratización de las criptomonedas sin permiso). IEEE Security & Privacy on the Blockchain (IEEE S&B). doi :10.1109/EuroSPW.2017.46. Archivado desde el original el 12 de noviembre de 2020. Consultado el 21 de diciembre de 2020 .
34. Divya Siddarth; Sergey Ivliev; Santiago Siri; Paula Berman (13 de octubre de 2020). "¿Quién vigila a los vigilantes? Una revisión de los 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. 1.er taller sobre sistemas de redes sociales - SocialNets '08. págs. 31–36. doi :10.1145/1435497.1435503. ISBN 978-1-60558-124-8. Recuperado el 28 de octubre de 2020 .
36. Gal Shahaf; Ehud Shapiro; Nimrod Talmon (octubre de 2020). Identificadores personales genuinos y garantías mutuas para el crecimiento de comunidades resilientes a la sibila. Conferencia internacional sobre 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; Alexander Frolov; Tyler Kell; Tyrone Lobban; Christine Moy; Ari Juels; Andrew Miller (28 de septiembre de 2020). «CanDID: Identidad descentralizada Can-Do con compatibilidad heredada, resistencia a Sybil y responsabilidad» (PDF) . Archivado (PDF) del original el 9 de octubre de 2022. Consultado el 28 de octubre de 2020 .
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). "Wait-Free Synchronization" (PDF) . ACM Transactions on Programming Languages ​​and Systems . 11 (1): 124–149. doi :10.1145/114005.102808. S2CID  2181446. Archivado (PDF) desde el original el 5 de junio de 2011 . Consultado el 19 de diciembre de 2011 .
40. Imbs, Damien; 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 computación distribuida . Association for Computing Machinery. págs. 26–35. doi :10.1145/1835698.1835705. ISBN . 978-1-60558-888-9. S2CID  3179361. Archivado (PDF) del original el 27 de enero de 2022 . Consultado el 22 de abril de 2021 .
41. Fich, Faith; 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 la ACM sobre Principios de computación distribuida . Association for Computing Machinery. págs. 80–87. CiteSeerX 10.1.1.96.9340 . doi :10.1145/1011767.1011780. ISBN .  1-58113-802-4.S2CID 9313205  .

Lectura adicional

• 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 de k-set sin espera es imposible: la topología del conocimiento público". Revista SIAM de informática . 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