Hispanopedia Wiki
Articulo de referencia

Consenso (informática)

Un problema fundamental en la computación distribuida y los sistemas multiagente es lograr la fiabilidad general del sistema en presencia de varios procesos defectuosos. Esto su...

Hispanopedia WikiContenido en espanolLectura gratuita

Un problema fundamental en la computación distribuida y los sistemas multiagente es lograr la fiabilidad general del sistema en presencia de varios procesos defectuosos. Esto suele requerir la coordinación de procesos para alcanzar un consenso , es decir, acordar algún valor de datos necesario durante el cálculo. Ejemplos de aplicaciones de consenso incluyen acordar qué transacciones confirmar en una base de datos y en qué orden, la replicación de máquinas de estado y las transmisiones atómicas . Las aplicaciones del mundo real que a menudo requieren consenso incluyen la computación en la nube , la sincronización de relojes , PageRank , la formación de opiniones, las redes eléctricas inteligentes , la estimación de estado , el control de vehículos aéreos no tripulados (y múltiples robots/agentes en general), el equilibrio de carga , la cadena de bloques , entre 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 estos procesos (o agentes) pueden fallar o ser poco fiables, por lo que los protocolos de consenso deben ser tolerantes a fallos o resilientes. Los procesos deben proponer sus valores candidatos, comunicarse entre sí y acordar un único valor de consenso.

El problema del consenso es fundamental para el control de sistemas multiagente. Un enfoque para generar consenso consiste en que todos los procesos (agentes) se pongan de acuerdo en un valor mayoritario. En este contexto, la mayoría requiere al menos un voto más de la mitad de los votos disponibles (donde cada proceso tiene un voto). Sin embargo, uno o más procesos defectuosos pueden distorsionar el resultado, de modo que no se alcance el consenso o se alcance de forma incorrecta.

Los protocolos que resuelven problemas de consenso están diseñados para manejar 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 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 solo puede decidir un valor de salida una vez, y esta decisión es irrevocable. Un método es correcto en una ejecución si no experimenta fallas. Un protocolo de consenso que tolera fallas de parada debe satisfacer las siguientes propiedades. [ 1 ]

Terminación
En última instancia, todo proceso correcto determina algún valor.
Integridad
Si todos los procesos correctos propusieran el mismo valorv{\displaystyle v}, entonces cualquier proceso correcto debe decidirv{\displaystyle v}.
Acuerdo
Todo proceso correcto debe coincidir en el mismo valor.

Según la aplicación, pueden ser apropiadas variaciones en la definición de integridad . Por ejemplo, un tipo de integridad más débil sería que el valor de la decisión fuera igual a un valor propuesto por algún proceso correcto, no necesariamente por todos ellos. [ 1 ] En la literatura también existe una condición conocida como validez , que se refiere a la propiedad de que un mensaje enviado por un proceso debe ser entregado. [ 1 ]

Se dice que un protocolo que puede garantizar correctamente el consenso entre n procesos, de los cuales como máximo t fallan, es t-resistente .

Al evaluar el rendimiento de los protocolos de consenso, dos factores clave son el tiempo de ejecución y la complejidad de los mensajes . El tiempo de ejecución se expresa en notación Big O como el número de rondas de intercambio de mensajes en función de ciertos 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 generado por 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 computación pueden definir un "problema de consenso". Algunos modelos pueden trabajar con grafos totalmente conectados, mientras que otros pueden trabajar 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 constituyen 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 que los receptores conocen la fuente de cada mensaje que reciben. Algunos modelos asumen una forma de autenticación más robusta y transferible , donde cada mensaje está firmado por el remitente, de modo que el receptor conoce no solo la fuente inmediata de cada mensaje, sino también al participante que lo creó inicialmente. Este tipo de autenticación más robusta se logra mediante firmas digitales, y cuando está disponible, los protocolos pueden tolerar un mayor número de fallos. [ 2 ]

Los dos modelos de autenticación diferentes suelen denominarse modelos de comunicación oral y de comunicación escrita . En un modelo de comunicación oral, se conoce la fuente inmediata de la información, mientras que en los modelos de comunicación escrita, más robustos, el receptor conoce en cada paso no solo la fuente inmediata del mensaje, sino también su historial de comunicación. [ 3 ]

Entradas y salidas del consenso

En los protocolos de consenso de valor único más tradicionales , como Paxos , los nodos que cooperan se ponen de acuerdo en un único valor, como un número entero, que puede ser de tamaño variable para codificar metadatos útiles , como una transacción registrada en una base de datos.

Un caso especial del problema de consenso de valor único, denominado consenso binario , restringe el dominio de entrada y, por lo tanto, el de salida, a un único dígito binario {0,1}. Si bien no son muy útiles por sí mismos, los protocolos de consenso binario suelen ser útiles como componentes básicos en protocolos de consenso más generales, especialmente para el consenso asíncrono.

En los protocolos de consenso multivalorados , como Multi-Paxos y Raft , el objetivo es llegar a un acuerdo no solo sobre un único valor, sino sobre una serie de valores a lo largo del tiempo, formando un historial que crece progresivamente. Si bien el consenso multivalorado puede lograrse de forma simplista ejecutando varias iteraciones sucesivas de un protocolo de consenso monovalorado, numerosas optimizaciones y otras consideraciones, como la compatibilidad con la reconfiguración, pueden hacer que los protocolos de consenso multivalorados sean más eficientes en la práctica.

Fallos catastróficos y bizantinos

Un proceso puede sufrir dos tipos de fallos: un fallo por caída o un fallo bizantino . Un fallo por caída se produce cuando un proceso se detiene abruptamente y no se reanuda. Los fallos bizantinos son fallos en los que no se impone ninguna condición. Por ejemplo, pueden ocurrir como resultado de acciones maliciosas de un adversario. Un proceso que sufre un fallo bizantino puede enviar datos contradictorios o conflictivos a otros procesos, o puede entrar en estado de espera y reanudar su actividad tras una larga demora. De los dos tipos de fallos, los fallos bizantinos son mucho más perjudiciales.

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

Una versión más sólida del consenso que tolera fallos bizantinos se obtiene reforzando la restricción de integridad:

Integridad
Si un proceso correcto decide v , entonces v debe haber sido propuesto por algún proceso correcto.

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 asume que todas las comunicaciones se desarrollan en rondas . En una ronda, un proceso puede enviar todos los mensajes que necesita, al tiempo que recibe todos los mensajes de los demás procesos. De esta manera, ningún mensaje de una ronda puede influir en los mensajes enviados dentro de la misma ronda.

El resultado de imposibilidad de FLP para el consenso determinista asíncrono

En un sistema distribuido de paso de mensajes totalmente asíncrono, en el que al menos un proceso puede sufrir un fallo 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 ]

En un modelo asíncrono, algunos tipos de fallos pueden ser gestionados por un protocolo de consenso síncrono. 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 sortear el resultado de imposibilidad de FLP al lograr seguridad y vivacidad 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 asumen 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 autorizado a un grupo 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 vulnerar incluso un algoritmo de consenso bizantino, simplemente creando suficientes participantes virtuales para superar el umbral de tolerancia a fallos.

Un protocolo de consenso sin permisos , en cambio, 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 del ataque Sybil . Bitcoin introdujo el primer protocolo de consenso sin permisos utilizando prueba de trabajo y una función de ajuste de dificultad, en el que los participantes compiten para resolver acertijos hash criptográficos y ganan probabilísticamente el derecho a confirmar 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 sin permisos 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.

Finalización de la transmisión confiable

Un conjunto de n procesos, numerados del 0 al n − 1 , se comunican enviándose mensajes entre sí. El proceso 0 debe transmitir un valor v a todos los procesos de tal manera que:

  1. Si el proceso 0 es correcto, entonces cada proceso correcto recibe 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 coincidir en el mismo valor.
  • Validez débil : Para cada proceso correcto, su salida debe ser la entrada de algún proceso correcto.
  • Validez sólida : 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, en última instancia, decidir un valor de salida.

Consistencia interactiva débil

Para n procesos en un sistema parcialmente síncrono (el sistema alterna entre períodos de buena y mala 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 v , entonces todos los procesos correctos reciben v o nada (propiedad de integridad).
  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, ya que la solución para un problema en un tipo de modelo puede ser la solución para otro problema en otro tipo de modelo. Por ejemplo, una solución al problema del General Bizantino Débil en un modelo de paso de mensajes autenticado síncrono conduce a una solución para la Consistencia Interactiva Débil. [ 8 ] Un algoritmo de consistencia interactiva 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 resolubilidad para algunos problemas de concordancia

Existe un protocolo síncrono anónimo t -resiliente que resuelve el problema de los generales bizantinos , [ 10 ] [ 11 ] si ⁠ t / n ⁠ < ⁠ 1 / 3 ⁠ y el caso de los generales bizantinos débiles [ 8 ] donde t es el número de fallos y n es el número de procesos.

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

En un sistema totalmente asíncrono no existe una solución de consenso que pueda tolerar uno o más fallos por caída, 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 el Premio Dijkstra por este importante trabajo. El resultado FLP se ha verificado mecánicamente y se mantiene incluso bajo supuestos de equidad . [ 13 ] Sin embargo, FLP no afirma que nunca se pueda alcanzar el consenso: simplemente que, bajo los supuestos del modelo, ningún algoritmo puede alcanzar siempre el consenso en un tiempo limitado. En la práctica, es muy improbable que esto ocurra.

Algunos protocolos de consenso

El algoritmo de consenso Paxos , creado por Leslie Lamport , y sus variantes, como Raft , se utilizan ampliamente en sistemas de computación distribuida y en la nube . Estos algoritmos suelen ser síncronos, dependen de un líder elegido para avanzar y solo toleran fallos del sistema, no errores bizantinos.

Se han desarrollado otros protocolos, como Cerberus, para aplicar el consenso tolerante a fallos bizantinos a libros de contabilidad distribuidos fragmentados y han sido objeto de análisis académico. [ 14 ]

Un ejemplo de un protocolo de consenso binario de tiempo polinomial que tolera fallos bizantinos es el algoritmo Phase King de Garay y Berman. [ 15 ] El algoritmo resuelve el consenso en un modelo de paso de mensajes síncrono con n procesos y hasta f fallos, siempre que n > 4 f . En el algoritmo Phase King, hay f + 1 fases, con 2 rondas por fase. Cada proceso mantiene un registro de su salida preferida (inicialmente igual al valor de entrada del propio proceso). En la primera ronda de cada fase, cada proceso difunde su propio valor preferido a todos los demás procesos. Luego recibe los valores de todos los procesos y determina cuál 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 es designado rey de la fase. El rey difunde el valor mayoritario que observó en la primera ronda y actúa como desempate. Luego, cada proceso actualiza su valor preferido de la siguiente manera. Si el recuento del valor mayoritario que el proceso observó 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 generan sus valores preferidos.

Google ha implementado una biblioteca de servicio de bloqueo distribuido llamada Chubby . [ 16 ] Chubby mantiene la información de bloqueo en archivos pequeños que se almacenan en una base de datos replicada para lograr una alta disponibilidad ante fallos. La base de datos se implementa sobre una capa de registro tolerante a fallos basada en el algoritmo de consenso Paxos . En este esquema, los clientes de Chubby se comunican con el maestro Paxos para acceder/actualizar el registro replicado; es decir, leer/escribir en los archivos. [ 17 ]

Muchos juegos de estrategia en tiempo real en línea peer-to-peer utilizan un protocolo de sincronización modificado como protocolo de consenso para gestionar el estado del juego entre los jugadores. Cada acción del juego genera una variación en el estado del juego que se transmite a todos los demás jugadores, junto con un hash del estado total. Cada jugador valida el cambio aplicando la variación a su propio estado y comparando los hashes. Si los hashes no coinciden, se realiza una votación y los jugadores cuyo estado sea minoritario se desconectan y se eliminan del juego (lo que se conoce como desincronización).

Otro enfoque bien conocido se denomina algoritmos de tipo MSR, que se han utilizado ampliamente en campos que van desde la informática hasta la teoría de control . [ 18 ] [ 19 ] [ 20 ]

Protocolos de consenso sin permisos

Bitcoin utiliza 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 peer-to-peer . Para extender la cadena de bloques o 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. El nodo que primero resuelve dicho rompecabezas ve su propuesta de versión del siguiente bloque de transacciones añadida al libro mayor y finalmente aceptada por todos los demás nodos. Dado que cualquier nodo en la red puede intentar resolver el problema de 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. Fuente.

Otras criptomonedas (por ejemplo, Ethereum , NEO, STRATIS, ...) utilizan la prueba de participación , en la que los nodos compiten para añadir bloques y obtener recompensas asociadas en proporción a la participación , es decir, la criptomoneda existente asignada y bloqueada o apostada durante un período de tiempo determinado. Una ventaja de la prueba de participación sobre el sistema de prueba de trabajo es el alto consumo energético que requiere este último. Por ejemplo, se estima que la minería de bitcoin (2018) consume una cantidad de energía no renovable similar a la de países enteros como la República Checa o Jordania, mientras que el consumo energético total de Ethereum, la mayor red de prueba de participación, es ligeramente inferior al de 205 hogares estadounidenses promedio. [ 32 ] [ 33 ] [ 34 ]

Algunas criptomonedas, como Ripple, utilizan un sistema de nodos de validación para validar el libro mayor. Este sistema utilizado por Ripple, llamado Algoritmo de Consenso del Protocolo Ripple (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 superen el umbral mínimo pasan a la siguiente ronda;
Paso 4: la ronda final requiere un 80% de acuerdo. [ 35 ]

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

En contraste con las reglas de participación sin permiso mencionadas anteriormente, que 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 buscan otorgar a cada participante humano real exactamente una unidad de poder de voto en el consenso sin permiso, independientemente de la inversión económica. [ 36 ] [ 37 ] Los enfoques propuestos para lograr una distribución de uno por persona del poder de consenso para la prueba de personalidad incluyen partidos con seudónimos físicos, [ 38 ] redes sociales, [ 39 ] identidades gubernamentales seudonimizadas, [ 40 ] y biometría. [ 41 ]

Número de consenso

Para resolver el problema del consenso en un sistema de memoria compartida, es necesario introducir objetos concurrentes. Un objeto concurrente, o compartido, es una estructura de datos que facilita la comunicación entre procesos concurrentes para alcanzar un acuerdo. Las implementaciones tradicionales que utilizan secciones críticas corren el riesgo de fallar si algún proceso se detiene dentro de la sección crítica o permanece inactivo durante un tiempo excesivamente prolongado. Los investigadores definieron la ausencia 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 mediante dicho objeto en una implementación sin esperas. [ 42 ] Los objetos con un número de consenso n pueden implementar cualquier objeto con un número de consenso n o inferior, pero no pueden implementar ningún objeto con un número de consenso superior. Los números de consenso conforman lo que se denomina la jerarquía de objetos de sincronización de Herlihy . [ 43 ]

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 las pilas y las colas solo pueden resolver el consenso entre dos procesos. Sin embargo, algunos objetos concurrentes son universales (indicados en la tabla con ∞ ), lo que significa que pueden resolver el consenso entre cualquier número de procesos y pueden simular cualquier otro objeto mediante una secuencia de operaciones. [ 42 ]

Véase también

Referencias

  1. 1 2 3 Coulouris, George; Dollimore, Jean; Kindberg, Tim (2001). Sistemas distribuidos: conceptos y diseño (3.ª  ed.). Addison-Wesley. pág.  452. ISBN 978-0201-61918-8.
  2. 1 2 3 4 Dolev, D.; Strong, HR (1983). "Algoritmos autenticados para el acuerdo bizantino". SIAM Journal on Computing . 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 del original el 5 de enero de 2020. Recuperado el 28 de mayo de 2019 .
  4. ↑ Aguilera, MK (2010). "Tropezando con la investigación de consenso: malentendidos y problemas". Replicación . Notas de clase en ciencias de la computación. Vol. 5959. pp. 59–72 . doi : 10.1007/978-3-642-11294-2_4 . ISBN   978-3-642-11293-5.
  5. 1 2 Fischer, MJ ; Lynch, NA ; Paterson, MS (1985). "Imposibilidad del consenso distribuido con un proceso defectuoso" (PDF) . Journal of the ACM . 32 (2): 374– 382. doi : 10.1145/3149.214121 . S2CID 207660233 . Archivado (PDF) del original el 30-01-2023 . Recuperado el 13-11-2017 . 
  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 del 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 bizantinos con consistencia interactiva débil" . Principios de sistemas distribuidos . Notas de clase en ciencias de la computación. 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.
  8. 1 2 Lamport, L. (1983). "El problema de los generales bizantinos débiles" . Journal of the 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 reseña)" (PDF) . Archivado del original (PDF) el 22 de abril de 2014. Recuperado el 21 de abril de 2014 .
  10. 1 2 3 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) del original el 07-02-2017 . Recuperado el 29-08-2015 .  
  11. ↑ Lamport, Leslie; Marshall Pease; Robert Shostak (abril de 1980). "Alcanzando un acuerdo en presencia de fallas" (PDF) . Journal of the ACM . 27 (2): 228– 234. CiteSeerX 10.1.1.68.4044 . doi : 10.1145/322186.322188 . S2CID 6429068. Archivado (PDF) del original el 28 de enero de 2007. Recuperado el 25 de julio de 2007 .  
  12. ^ Attiya, Hagit (2004). Computación distribuida (2ª ed.). Wiley. págs. 101 a 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.), Interactive Theorem Proving , Lecture Notes in Computer Science, vol. 9807, Springer International Publishing, pp. 107–122 , doi : 10.1007/978-3-319-43144-4_7 , ISBN    978-3-319-43144-4
  14. ^ Jalalzai, Mohammad; Gencer, A. Ercument; Katsipoulakis, Manos; Vogels, Werner; Gessner, Gregorio; Kapritsos, Manos (2023). "Cerberus: el protocolo de consenso de Radix" . Registro SIGMOD . 52 (4): 58– 65. doi : 10.5070/SR33161345 .
  15. ↑ Berman, Piotr; Garay, Juan A. (1993). "Cloture Votes: n/4-resilient Distributed Consensus in t + 1 rounds". Theory of Computing Systems . 2. 26 : 3– 19. doi : 10.1007/BF01187072 . S2CID 6102847 . 
  16. ↑ Burrows, M. (2006). El servicio de bloqueo Chubby para sistemas distribuidos débilmente acoplados (PDF) . Actas del 7.º Simposio sobre Diseño e Implementación de Sistemas Operativos. USENIX Association, Berkeley, CA, EE. UU. pp. 335–350 . Archivado (PDF) del original el 14 de diciembre de 2009. Consultado el 28 de octubre de 2014 . 
  17. ↑ 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 del original (PDF) el 12 de diciembre de 2014. Recuperado el 6 de febrero de 2008 . 
  18. ↑ LeBlanc, Heath J. (abril de 2013). "Consenso asintótico resiliente en redes robustas". IEEE Journal on Selected Areas in Communications . 31 (4): 766– 781. Bibcode : 2013IJSAC..31..766L . CiteSeerX 10.1.1.310.5354 . doi : 10.1109/JSAC.2013.130413 . S2CID 11287513 .  
  19. ↑ Dibaji, SM (mayo de 2015). "Consenso de sistemas multiagente de segundo orden en presencia de fallos localmente limitados". Systems & Control Letters . 79 : 23–29 . doi : 10.1016/j.sysconle.2015.02.005 .
  20. ↑ Dibaji, SM (julio de 2017). "Consenso resiliente de redes de agentes de segundo orden: reglas de actualización asíncronas con retrasos". Automatica . 81 : 123–132 . arXiv : 1701.03430 . Bibcode : 2017arXiv170103430M . doi : 10.1016/j.automatica.2017.03.008 . S2CID 7467466 . 
  21. ↑ Ben-Or, Michael (1983). "Otra ventaja de la libre elección (resumen extendido): protocolos de acuerdo completamente asíncronos". 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 .  
  22. ↑ Hellings, Jelle; Sadoghi, Mohammad (2023). "Cerberus: Procesamiento de transacciones minimalista multi-fragmento resistente a la manipulación bizantina" . Journal of Systems Research . 3 (1). doi : 10.5070/SP24360340 (inactivo el 10 de enero de 2026).{{cite journal}}: CS1 maint: DOI inactivo desde enero de 2026 ( enlace )
  23. ↑ Dolev, Danny; Fisher, Michael J.; Fowler, Rob; Lynch, Nancy; Strong, H. Raymond (1982). "Un algoritmo eficiente para el acuerdo bizantino sin autenticación" . Information and Control . 52 (3): 257– 274. doi : 10.1016/S0019-9958(82)90776-8 .
  24. ↑ Feldman, Pesech; Micali, Sylvio (1997). "Un protocolo probabilístico óptimo para el acuerdo bizantino síncrono". SIAM Journal on Computing . 26 (4): 873– 933. doi : 10.1137/S0097539790187084 .
  25. ↑ Katz, Jonathan; Koo, Chiu-Yuen (2006). "Sobre protocolos de ronda constante esperada para el acuerdo bizantino". Avances en criptología - CRYPTO 2006. Notas de clase en ciencias de la computación. Vol. 4117. págs. 445–462 . doi : 10.1007/11818175_27 . ISBN   978-3-540-37432-9.
  26. ↑ Castro, Miguel; Liskov, Barbara (1999). "Tolerancia práctica a fallos bizantinos" (PDF) . Actas del Tercer Simposio sobre Diseño e Implementación de Sistemas Operativos, Nueva Orleans, EE. UU., febrero de 1999. Archivado ( PDF) del original el 4 de marzo de 2018. Consultado el 28 de mayo de 2019 .
  27. ↑ Miller, Andrew; Xia, Yu; Croman, Kyle; Shi, Elaine ; Song, Dawn (octubre de 2016). "El tejón melero de los protocolos BFT" (PDF) . CCS '16: Actas de la Conferencia ACM SIGSAC de 2016 sobre seguridad informática y de comunicaciones . págs. 31–42 . doi : 10.1145/2976749.2978399 . Archivado (PDF) del original el 3 de junio de 2023. Recuperado el 4 de julio de 2023 . 
  28. ↑ Abraham, Ittai; Devadas, Srinivas; Dolev, Danny; Nayak, Kartik; Ren, Ling (11 de septiembre de 2017). "Consenso bizantino síncrono eficiente" (PDF) . Cryptology ePrint Archive . Documento 2017/307. Archivado (PDF) del original el 4 de julio de 2023. Recuperado el 4 de julio de 2023 .
  29. ↑ Micali, Sylvio (19 de marzo de 2018). "Acuerdo bizantino trivializado" (PDF) . Cambridge, MA: CSAIL, MIT. Archivado (PDF) del original el 7 de diciembre de 2022. Recuperado el 28 de mayo de 2019 .
  30. ^ Chen, Jing; Micali, Silvio (2016). "ALGORANDO". arXiv : 1607.01341v9 [ cs.CR ].
  31. ↑ Locher, Thomas (2020). "Acuerdo bizantino rápido para libros de contabilidad distribuidos con permisos". Actas del 32.º Simposio ACM sobre paralelismo en algoritmos y arquitecturas . SPAA '20. Nueva York, NY, EE. UU.: Association for Computing Machinery. págs. 371–382 . doi : 10.1145/3350755.3400219 . 
  32. ↑ Irfan, Umair (18 de junio de 2019). "Bitcoin consume muchísima energía. ¿De dónde sale toda esa electricidad?" . Vox . Archivado del original el 16 de febrero de 2023. Consultado el 28 de agosto de 2019 .
  33. ↑ "La fusión: implicaciones en el consumo de electricidad y la huella de carbono de la red Ethereum" . 7 de septiembre de 2022. Archivado del original el 5 de septiembre de 2023. Consultado el 5 de septiembre de 2023 .
  34. ↑ "Consumo de electricidad per cápita en todo el mundo en 2022, por país seleccionado" . Statista . Archivado del original el 5 de septiembre de 2023. Consultado el 5 de septiembre de 2023 .
  35. ↑ Schwartz, David; Youngs, Noah; Britto, Arthur (2014). "El algoritmo de consenso del protocolo Ripple" (PDF) . Ripple Labs (borrador). Archivado (PDF) del original el 29 de agosto de 2017. Recuperado el 3 de julio de 2023 .
  36. ↑ Borge, Maria; Kokoris-Kogias, Eleftherios; Jovanovic, Philipp; Gasser, Linus; Gailly, Nicolas; Ford, Bryan (2017). «Prueba de personalidad: Redemocratizando las criptomonedas sin permisos». 2017 IEEE European Symposium on Security and Privacy Workshops (EuroS&PW) . pp. 23–26 . doi : 10.1109/EuroSPW.2017.46 . ISBN  978-1-5386-2244-5.
  37. ↑ Siddarth, Divya; Ivliev, Sergey; Siri, Santiago; Berman, Paula (13 de octubre de 2020). "¿Quién vigila a los vigilantes? Una revisión de los enfoques subjetivos para la resistencia a Sybil en los protocolos de prueba de personalidad". arXiv : 2008.05300 [ cs.CR ].
  38. ↑ 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. Consultado el 28 de octubre de 2020 .
  39. ↑ Shahaf, Gal; Shapiro, Ehud; Talmon, Nimrod (octubre de 2020). «Identificadores personales genuinos y garantías mutuas para el crecimiento comunitario resistente a ataques Sybil» . Informática social . Notas de clase en informática. Vol. 12467. págs. 320–332 . arXiv : 1904.09630 . doi : 10.1007/978-3-030-60975-7_24 . ISBN   978-3-030-60974-0.
  40. ↑ Maram, Deepak; Malvai, Harjasleen; Zhang, Fan; Jean-Louis, Nerla; Frolov, Alexander; Kell, Tyler; Lobban, Tyrone; Moy, Christine; Juels, Ari; Miller, Andrew (28 de septiembre de 2020). "CanDID: Identidad descentralizada Can-Do con compatibilidad heredada, resistencia a Sybil y rendición de cuentas" (PDF) . Archivado (PDF) del original el 9 de octubre de 2022. Recuperado el 28 de octubre de 2020 .
  41. ^ Hajialikhani, Mohammad Javad; Jahanara, Mohammad Mahdi (20 de junio de 2018). "UniqueID: prueba descentralizada de ser humano único". arXiv : 1806.07583 [ cs.CR ].
  42. 1 2 Herlihy, Maurice (enero de 1991). "Sincronización sin espera" ( PDF) . ACM Transactions on Programming Languages ​​and Systems . 11 (1): 124– 149. doi : 10.1145/114005.102808 . S2CID 2181446. Archivado (PDF) del original el 5 de junio de 2011. Recuperado el 19 de diciembre de 2011 . 
  43. ↑ 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 . Recuperado el 22 de abril de 2021 . 
  44. ↑ 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 . 

Lecturas adicionales

  • Herlihy, M.; Shavit, N. (1999). "La estructura topológica de la computabilidad asíncrona". Journal of the ACM . 46 (6): 858. CiteSeerX 10.1.1.78.1455 . doi : 10.1145/331524.331529 . S2CID 5797174 .  
  • Saks, M.; Zaharoglou, F. (2000). "Es imposible lograr un acuerdo de k-conjuntos sin esperas: la topología del conocimiento público". SIAM Journal on Computing . 29 (5): 1449– 1483. doi : 10.1137/S0097539796307698 .
  • Bashir, Imran. "Consenso en Blockchain". Blockchain Consensus - Una introducción a los protocolos de consenso clásicos, de blockchain y cuánticos . ISBN 978-1-4842-8178-9Apress, Berkeley, CA, 2022. doi : 10.1007/978-1-4842-8179-6
Lecturas relacionadas
6 articulos
Computación distribuidaComputación distribuidaLa computación distribuida es un campo de la informática que estudia los sistemas distribuidos , definidos como sistemas informáticos cuyos compone...Multi-agent systemMulti-agent systemA multi-agent system (MAS) or "self-organized system" is a computational system composed of multiple interacting intelligent agents.[1][2][3] Multi...replicación de máquina de estadosEn informática , la replicación de máquinas de estado ( SMR ) o enfoque de máquina de estado es un método general para implementar un servicio tole...Computación en la nubeMetáfora de la computación en la nube: el grupo de elementos en red que proporcionan servicios no necesita ser abordado o administrado individualme...Sincronización de relojSincronización de relojLa sincronización de relojes es un tema de la ciencia informática y la ingeniería que tiene como objetivo coordinar relojes que de otro modo serían...PageRankPageRankPageRank ( PR ) es un algoritmo que utiliza Google Search para clasificar las páginas web en los resultados de búsqueda . Su nombre hace referencia...