Consenso (informática)

Un problema fundamental en la computación distribuida y los sistemas de múltiples agentes 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 llegar a un consenso o acordar algún valor de datos que se necesita durante el cálculo. Las aplicaciones de ejemplo de consenso incluyen acordar qué transacciones comprometer con una base de datos en qué orden, replicación de la máquina 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 reloj , PageRank , formación de opiniones, redes eléctricas inteligentes ,estimación de estado , control de UAV (y múltiples robots / agentes en general), balanceo de carga , blockchain y otros.

Descripción del problema

El problema del consenso requiere el acuerdo entre varios procesos (o agentes) para un valor de datos único. 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 resistentes. De alguna manera, los procesos deben presentar sus valores candidatos, comunicarse entre sí y acordar un valor de consenso único.

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 una más de la mitad de los votos disponibles (donde cada proceso recibe un voto). Sin embargo, uno o más procesos defectuosos pueden sesgar el resultado resultante de tal manera que no se llegue a un consenso o se logre incorrectamente.

Los protocolos que resuelven problemas de consenso están diseñados para hacer frente a un número limitado de procesos defectuosos . Estos protocolos deben satisfacer una serie de requisitos para ser útiles. Por ejemplo, un protocolo trivial podría hacer que todos los procesos generen un valor binario 1. Esto no es útil y, por lo tanto, el requisito se modifica de manera que la salida debe depender de alguna manera 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 proceso se llama correcto en una ejecución si no experimenta una falla. Un protocolo de consenso que tolere la detención de fallas debe satisfacer las siguientes propiedades. ^[1]

Terminación

Eventualmente, cada proceso correcto decide algún valor.

Integridad

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

Convenio

Todo proceso correcto debe coincidir en el mismo valor.

Las variaciones en la definición de integridad pueden ser apropiadas, según la aplicación. Por ejemplo, un tipo de integridad más débil sería que el valor de decisión fuera igual a un valor propuesto por algún proceso correcto, no necesariamente todos. ^[1] La condición de integridad también se conoce como validez en la literatura. ^[1]

Un protocolo que puede garantizar correctamente el consenso entre n procesos de los que como máximo t fallan se dice que es t-resilient .

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 de los mensajes se refiere a la cantidad de tráfico de mensajes que genera el protocolo. Otros factores pueden incluir el uso de memoria y el tamaño de los mensajes.

Modelos de computación

Los distintos 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 , en la que cada mensaje está firmado por el remitente, de modo que un receptor conoce no solo la fuente inmediata de cada mensaje, sino también el participante que inicialmente creó el mensaje. Este tipo de autenticación más fuerte se logra mediante firmas digitales, y cuando esta forma de autenticación más fuerte está disponible, los protocolos pueden tolerar un mayor número de fallas. ^[2]

Los dos modelos de autenticación diferentes se denominan a menudo modelos de comunicación oral y de 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, cada paso a lo largo del receptor aprende no solo 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 comprometida con una base de datos.

Un caso especial del problema de consenso de valor único, llamado consenso binario , restringe la entrada, y por lo 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 binario suelen ser útiles como bloques de construcción en protocolos de consenso más generales, especialmente para el consenso asincrónico.

En 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 de un protocolo de consenso de valor único en sucesión, 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.

Fallos accidentales y bizantinos

Hay dos tipos de fallas que puede sufrir un proceso, una falla por colisión o una falla bizantina . Una falla por colisión ocurre cuando un proceso se detiene abruptamente y no se reanuda. Los fallos bizantinos son fallos en los que no se impone absolutamente 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 dormir y luego reanudar la actividad después de un retraso prolongado. De los dos tipos de fallas, las fallas bizantinas son mucho más disruptivas.

Por lo tanto, un protocolo de consenso que tolere las fallas bizantinas debe ser resistente a todos los posibles errores que puedan ocurrir.

Una versión más sólida del consenso que tolera las fallas bizantinas se da al fortalecer 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 a menudo son intrínsecamente asincrónicas, es más práctico y, a menudo, más fácil modelar sistemas síncronos, ^[4] dado que los sistemas asíncronos naturalmente involucran más problemas que los síncronos.

En los sistemas síncronos, se supone que todas las comunicaciones proceden en rondas . En una ronda, un proceso puede enviar todos los mensajes que necesita, mientras recibe 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.

El resultado de la 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 colisión , se ha demostrado en el famoso resultado de imposibilidad de FLP que un algoritmo determinista para lograr consenso es imposible. ^[5] Este resultado de imposibilidad se deriva de los escenarios de programación del peor de los casos, 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 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 una falla bizantina.

Los algoritmos de consenso aleatorios pueden eludir el resultado de imposibilidad de FLP logrando 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 suponen tradicionalmente que el conjunto de nodos participantes es fijo y se da desde el principio: es decir, que algún proceso de configuración previo (manual o automático) ha permitido a un grupo conocido particular de participantes que pueden autenticarse entre sí como miembros del grupo. En ausencia de un grupo cerrado tan bien definido con miembros autenticados, un ataque de 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 cualquier persona en la red se una dinámicamente y participe sin permiso previo, pero en cambio impone una forma diferente de costo artificial o barrera de entrada para mitigar la amenaza de ataque de 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 el hash criptográfico.rompecabezas y, probabilísticamente, ganar el derecho a comprometer bloques y ganar recompensas asociadas en proporción a su esfuerzo computacional invertido. Motivado en parte por el alto costo energético de este enfoque, los protocolos de consenso subsiguientes 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 .

Equivalencia de problemas de acuerdos

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

Finalización de la transmisión confiable

Artículo principal: Terminación de la transmisión confiable

Una colección de procesos, numerados desde para comunicarse mediante el envío de mensajes entre sí. El proceso debe transmitir un valor a todos los procesos tal 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 conoce como El problema 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.
• Terminación : todos los procesos deben finalmente decidir sobre un valor de salida

Consistencia interactiva débil

Para n procesos en un sistema parcialmente síncrono (el sistema alterna entre períodos buenos y malos de sincronía), cada proceso elige un valor privado. Los procesos se comunican entre sí por 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 , 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 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 coherencia interactiva débil. ^[8] Un algoritmo de consistencia interactivo 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 acuerdos

Hay un protocolo síncrono anónimo t-resiliente que resuelve el problema de los generales bizantinos , ^{[10] [11]} if 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 un algoritmo que resuelva el problema del consenso 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 discutir 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 totalmente asincrónico no existe una solución de consenso que pueda tolerar una o más fallas por colisión incluso cuando solo se requiera la propiedad de no trivialidad. ^[5] Este resultado a veces se denomina prueba de imposibilidad de FLP, que lleva el nombre de los autores Michael J. Fischer , Nancy Lynch y Mike Paterson, que recibieron un premio Dijkstra por este importante trabajo. Se ha verificado mecánicamente que el resultado de FLP se mantiene incluso bajo supuestos de equidad . ^[13] Sin embargo, FLP no afirma que nunca se pueda llegar a un consenso: simplemente que bajo los supuestos del modelo, ningún algoritmo siempre puede llegar a un consenso en un tiempo limitado. En la práctica, es muy poco probable que ocurra.

Algunos protocolos de consenso

El algoritmo de consenso de Paxos de Leslie Lamport , y variantes del mismo, como Raft , se utilizan de manera generalizada en sistemas de computación en la nube y distribuidos ampliamente implementados . Estos algoritmos son típicamente sincrónicos, dependen de un líder electo para progresar y toleran solo 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 ^[14] de Garay y Berman. 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 de fase rey, 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 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 el proceso observado en la primera ronda es mayor que n / 2 + f, el proceso cambia su preferencia a ese valor mayoritario; de lo contrario, usa 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 servicio 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 de 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 de igual a igual utilizan un protocolo Lockstep modificado como protocolo de consenso para administrar el estado del juego entre los jugadores en 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 de juego y comparando los valores hash del estado del juego. Si los hashes no están de acuerdo, se emite un voto y los jugadores cuyo estado de juego es minoritario se desconectan y eliminan del juego (lo que se conoce como desincronización).

Otro enfoque bien conocido se llama algoritmos de tipo MSR que se han utilizado ampliamente desde la informática hasta la teoría de control. ^{[17] [18] [19]}

Fuente	Sincronía	Autenticación	Umbral	Rondas	Notas
Pease-Shostak-Lamport [10]	Sincrónico	Oral	${\displaystyle n>3f}$	${\displaystyle f+1}$	comunicación total ${\displaystyle O(n^{f})}$
Pease-Shostak-Lamport [10]	Sincrónico	Escrito	${\displaystyle n>f+1}$	${\displaystyle f+1}$	comunicación total ${\displaystyle O(n^{f})}$
Ben-Or [20]	Asincrónico	Oral	${\displaystyle n>5f}$	${\displaystyle O(2^{n})}$ (esperado)	rondas esperadas cuando${\displaystyle O(1)}$${\displaystyle f<{\sqrt {n}}}$
Dolev y col. [21]	Sincrónico	Oral	${\displaystyle n>3f}$	${\displaystyle 2f+3}$	comunicación total ${\displaystyle O(f^{3}\log f)}$
Dolev-Strong [2]	Sincrónico	Escrito	${\displaystyle n>f+1}$	${\displaystyle f+1}$	comunicación total ${\displaystyle O(n^{2})}$
Dolev-Strong [2]	Sincrónico	Escrito	${\displaystyle n>f+1}$	${\displaystyle f+2}$	comunicación total ${\displaystyle O(nf)}$
Feldman-Micali [22]	Sincrónico	Oral	${\displaystyle n>3f}$	${\displaystyle O(1)}$ (esperado)
Katz-Koo [23]	Sincrónico	Escrito	${\displaystyle n>2f}$	${\displaystyle O(1)}$ (esperado)	Requiere PKI
PBFT [24]	Asincrónico (seguridad) - Sincrónico (vivacidad)	Oral	${\displaystyle n>3f}$
HoneyBadger [25]	Asincrónico	Oral	${\displaystyle n>3f}$	${\displaystyle O(\log n)}$ (esperado)	por comunicación tx : requiere cifrado de clave pública${\displaystyle O(n)}$
Abraham y col. [26]	Sincrónico	Escrito	${\displaystyle n>2f}$	${\displaystyle 8}$
Acuerdo bizantino hecho trivial [27] [28]	Sincrónico	Firmas	${\displaystyle n>3f}$	${\displaystyle 9}$ (esperado)	Requiere firmas digitales

Protocolos de consenso sin permiso

Bitcoin usa 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 peer-to-peer . Para extender la cadena de bloques de Bitcoin o el libro mayor distribuido , 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 tal acertijo tiene su versión propuesta del siguiente bloque de transacciones agregada al libro mayor y finalmente aceptada por todos los demás nodos. Como cualquier nodo de la red puede intentar resolver el problema de la prueba de trabajo, un ataque de Sybil es inviable en principio a menos que el atacante tenga más del 50% de los recursos computacionales de la red.

Otras criptomonedas (es decir, DASH, NEO, STRATIS, ...) usan 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 la criptomoneda existente asignada y bloqueada o apostada durante un 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, al menos con la tecnología actual. Como ejemplo, se estima que la minería de Bitcoin (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. ^[29]

Algunas criptomonedas, como Ripple, utilizan un sistema de validación de nodos 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 amalgama a 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 se pasan a la siguiente ronda; Paso 4: la ronda final requiere un acuerdo del 80% ^[30]

Otras reglas de participación utilizadas en los protocolos de consenso sin permiso para imponer barreras de entrada y resistir los ataques de sibila incluyen prueba de autoridad , prueba de espacio , prueba de quema o prueba de tiempo transcurrido. Estas alternativas están nuevamente motivadas en gran medida por la gran cantidad de energía computacional consumida por la prueba de trabajo. ^{[31] La} prueba de espacio es utilizada por criptomonedas como Burstcoin.

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 dar a cada participante humano real exactamente una unidad de poder de voto en consenso sin permiso, independientemente de la inversión económica. . ^{[32] [33]} 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, ^[34] redes sociales, ^[35] identidades seudonimizadas emitidas por el gobierno, ^[36] y biometría. ^[37]

Número de consenso

Para resolver el problema del consenso en un sistema de memoria compartida, se deben introducir objetos concurrentes. Un objeto concurrente, o un 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 enfrentan 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 alcanzar el consenso del objeto dado en una implementación sin espera. ^{[38] 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 más alto. Los números de consenso forman lo que se llama la jerarquía de objetos de sincronización de Herlihy. ^[39]${\displaystyle n}$${\displaystyle n}$

Número de consenso	Objetos
${\displaystyle 1}$	registros atómicos de lectura / escritura , mutex
${\displaystyle 2}$	probar y configurar , intercambiar , buscar y agregar , cola o pila sin espera
...	...
${\displaystyle 2n-2}$	asignación de n-registro
...	...
${\displaystyle \infty }$	comparar e intercambiar , enlace de carga / almacenamiento condicional , [40] movimiento e intercambio de memoria a memoria, cola con operación de inspección, búsqueda y desventajas, byte fijo

Según la jerarquía, los registros de lectura / escritura no pueden resolver el consenso incluso en un sistema de 2 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. ^[38]${\displaystyle \infty }$

Ver también

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

Referencias

1. Coulouris, George; Jean Dollimore ; Tim Kindberg (2001), Sistemas distribuidos: conceptos y diseño (tercera edición) , Addison-Wesley, p. 452, ISBN 978-0201-61918-8
2. Dolev, D .; Strong, HR (1983). "Algoritmos autenticados para 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 .
4. Aguilera, MK (2010). "Tropezar con la investigación de consenso: malentendidos y problemas". Replicación . Apuntes de conferencias en Ciencias de la Computación. 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 el tiempo y el espacio" . Revista de algoritmos . 14 (3): 414–431. doi : 10.1006 / jagm.1993.1022 .
7. Milosevic, Zarko; Martin Hutle; Andre Schiper (2009). Unificando algoritmos de consenso bizantino con consistencia interactiva débil . Principios de sistemas distribuidos, notas de clase en informática . Apuntes de conferencias en Ciencias de la Computación. 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.
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 poco fiables (una breve encuesta)" (PDF) . 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 .  
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), Blanchette, Jasmin Christian; Merz, Stephan (eds.), Verificación mecánica de una prueba constructiva para FLP , Lecture Notes in Computer Science, 9807 , Springer International Publishing, doi : 10.1007 / 978-3-319-43144-4_7 , ISBN 978-3-319-43144-4
14. Berman, Piotr; Juan A. Garay (1993). "Votos de Cloture: Consenso distribuido resiliente n / 4 en t + 1 rondas". Teoría de los sistemas informáticos . 2. 26 : 3-19. doi : 10.1007 / BF01187072 . S2CID 6102847 . 
15. Burrows, M. (2006). El servicio de candado Chubby para sistemas distribuidos de acoplamiento flexible (PDF) . Actas del 7º Simposio sobre Diseño e Implementación de Sistemas Operativos . Asociación USENIX Berkeley, CA, EE. UU. págs. 335–350.
16. C., Tushar; 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 computación distribuida . Portland, Oregón, 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 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 delimitadas localmente". Sistemas y cartas de 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ónicas con retrasos". Automatica . 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 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 (Informe técnico). doi : 10.1137 / S0097539790187084 .
23. Katz, Jonathan; Koo, Chiu-Yuen (2006). Sobre los protocolos esperados de ronda constante para el acuerdo bizantino . CRYPTO. doi : 10.1007 / 11818175_27 .
24. Castro, Miguel; Liskov, Barbara (1999). Tolerancia práctica a fallas bizantinas (PDF) . OSDI.
25. Miller, Andrew; Xia, Yu; Croman, Kyle; Shi, Elaine ; Canción, amanecer (2016). El tejón de miel de los protocolos BFT . CCS. doi : 10.1145 / 2976749.2978399 .
26. Abraham, Ittai; Devadas, Srinivas; Dolev, Danny; Nayak, Kartik; Ren, Ling (2017). Consenso bizantino sincrónico eficiente (Informe técnico).
27. Micali, Sylvio (2018). "Acuerdo bizantino hecho trivial" (PDF) .
28. Chen, Jing; Micali, Silvio (2016). "ALGORAND". arXiv : 1607.01341v9 [ cs.CR ].
29. Irfan, Umair (18 de junio de 2019). "Bitcoin es un acaparador de energía. ¿De dónde viene toda esa electricidad?" . Vox .
30. Schwartz D, YoungsN, Britto A. 2014 El algoritmo de consenso del protocolo Ripple
31. ¿Cuáles son las estrategias alternativas para la prueba de trabajo?
32. Maria Borge, Eleftherios Kokoris-Kogias, Philipp Jovanovic, Linus Gasser, Nicolas Gailly, Bryan Ford (29 de abril de 2017). Prueba de personalidad: redemocratización de las criptomonedas sin permiso . Seguridad y privacidad IEEE en Blockchain (IEEE S&B) . doi : 10.1109 / EuroSPW.2017.46 .
33. Divya Siddarth, Sergey Ivliev, Santiago Siri, Paula Berman (13 de octubre de 2020). "¿Quién mira a los vigilantes? Una revisión de enfoques subjetivos para Sybil-resistencia en la prueba de protocolos de personalidad". arXiv : 2008.05300 [ cs.CR ].
34. Ford, Bryan; Strauss, Jacob (1 de abril de 2008). Una base fuera de línea para seudónimos responsables en línea . 1er Taller de Sistemas de Redes Sociales - SocialNets '08 . págs. 31–6. doi : 10.1145 / 1435497.1435503 . ISBN 978-1-60558-124-8.
35. Gal Shahaf, Ehud Shapiro, Nimrod Talmon (octubre de 2020). Identificadores personales genuinos y garantías mutuas para el crecimiento de la comunidad resiliente a Sybil . Congreso Internacional de Informática Social . doi : 10.1007 / 978-3-030-60975-7_24 .
36. 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, Sybil-Resistance y responsabilidad" (PDF) .
37. Mohammad-Javad Hajialikhani, Mohammad-Mahdi Jahanara (20 de junio de 2018). "UniqueID: prueba descentralizada de ser humano único". arXiv : 1806.07583 .
38. Herlihy, Maurice. "Sincronización sin espera" (PDF) . Consultado el 19 de diciembre de 2011 .
39. 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 . Asociación de Maquinaria de Computación: 26–35. doi : 10.1145 / 1835698.1835705 . ISBN  9781605588889. S2CID  3179361 . Consultado el 22 de abril de 2021 .
40. 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 ACM sobre Principios de Computación Distribuida . Asociación de Maquinaria de Computación: 80–87. CiteSeerX 10.1.1.96.9340 . doi : 10.1145 / 1011767.1011780 . ISBN  1581138024. 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). "Acuerdo de 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 .