¿Por qué es tan importante el problema del consenso en la informática distribuida?

19

En la informática distribuida, el problema del consenso parece ser uno de los temas centrales que ha atraído una investigación intensiva. En particular, el artículo "Imposibilidad de consenso distribuido con un proceso defectuoso" recibió el Premio de papel influyente PODC 2001 .

Entonces, ¿por qué es tan importante el problema del consenso? ¿Qué podemos lograr con consenso tanto en teoría como en la práctica?

Cualquier referencia o exposición sería realmente útil.

reference-request big-picture dc.distributed-comp hengxina
fuente

Respuestas:

18

El documento que menciona es importante por 2 razones:

  1. Muestra que no existe un algoritmo de consenso determinista asíncrono que tolere incluso un solo fallo de bloqueo. Tenga en cuenta que en la configuración sincrónica , hay un algoritmo determinista que termina en rondas de cuando ≤ f procesa el bloqueo.F+1≤F
  2. Introduce la bivalencia y la univalencia de configuraciones (*), que se utilizan en muchos límites inferiores y pruebas de imposibilidad más adelante.

Aplicaciones

Una aplicación importante del problema del consenso es la elección de un coordinador o líder en un entorno tolerante a fallas para iniciar alguna acción global. Un algoritmo de consenso le permite hacer esto sobre la marcha, sin fijar un "supernodo" de antemano (lo que introduciría un único punto de falla).

Otra aplicación es mantener la coherencia en una red distribuida: suponga que tiene diferentes nodos de sensores que monitorean el mismo entorno. En el caso de que algunos de estos nodos de sensores se bloqueen (o incluso comiencen a enviar datos corruptos debido a una falla de hardware), un protocolo de consenso asegura la solidez frente a tales fallas.

(*) Una ejecución de un algoritmo distribuido es una secuencia de configuraciones. Una configuración es un vector de los estados locales de los procesos. Cada proceso ejecuta una máquina de estado determinista. Cualquier algoritmo de consenso correcto debe eventualmente alcanzar una configuración en la que cada proceso haya decidido (irrevocablemente) sobre el mismo valor de entrada. Una configuración es 1 - valent si, sin importar lo que haga el adversario, todas las extensiones posibles de C conducen a un valor de decisión de 1 . Análogamente, podemos definir 0 - valencia . Una configuración C es bivalente si ambas decisiones son accesibles desde CC1C10 0CC(cuál de los dos se alcanza depende del adversario). Claramente, ningún proceso puede haberse decidido en una configuración bivalente , ya que de lo contrario obtenemos una contradicción de acuerdo. Entonces, si podemos construir una secuencia infinita de tales configuraciones bivalentes, hemos demostrado que no hay un algoritmo de consenso en esta configuración.C

Peter
fuente
2
@AJed Como suplemento: He revisado la sincronización en papel de Maurice Herlihy y ahora puedo presentar una gran implicación teórica adicional del problema del consenso. Utilizando la idea del número de consenso , se puede demostrar que existe una jerarquía infinita de primitivas de sincronización, de modo que no se puede utilizar ninguna primitiva en un nivel para una implementación sin esperas de ninguna primitiva en niveles superiores. En pocas palabras, el problema de consenso se corta como una teoría unificada sobre la definición del poder relativo de las operaciones de sincronización primitivas. Es elegante
hengxin
1
Tengo algunas dificultades para comprender la prueba del resultado de imposibilidad de FLP. ¿Podrías darme algunas pistas? Consulte [Prueba de FLP] ( stackoverflow.com/q/15131730/1833118 ). Gracias.
hengxin
¿"donde cada proceso ha decidido" tal vez debería ser "donde cada proceso correcto ha decidido"?
nbro
Debes explicar quién es el adversario "sin importar lo que haga el adversario".
nbro
"todas las extensiones posibles de C", ¿qué quiere decir con "extensión de C"? ¿Qué es una extensión de una configuración, en general?
nbro
7

Muestra que no hay algoritmo determinista tolerante a fallas. Un resultado teórico bastante fuerte, que obliga a los diseñadores a tratar de manera diferente la tolerancia a fallas, algunas de las cuales son sincronización y aleatorización.

Comentario: en mi opinión, la sincronización es una suposición adicional del sistema que apenas se encuentra en aplicaciones prácticas.

Para referencias, consulte el enlace de Wikipedia . Consulte también este blog para aplicaciones prácticas

AJed
fuente
1
Sí, prefiero la aleatorización a la sincronización. El entorno en el que se reproduce la informática distribuida es muy pobre en el sentido de asincronización, retraso ilimitado, falla inesperada y demasiado no determinista. Mientras no sea perfecto, ¿por qué no usamos la aleatorización, logrando algunas garantías y evitando demasiada complejidad?
hengxin
1
Hablando de sincronización, simplemente no me gusta la suposición en teoría . Sin embargo, en la industria , la sincronización o sincronización parcial se aplica con frecuencia. Por ejemplo, Google's Spanner es una base de datos replicada sincrónicamente distribuida globalmente . Me hace menos decisivo. ¿Cuál es tu opinión?
hengxin
Supongo que es mejor ver cómo se implementa la sincronización allí. Pero es una referencia muy interesante. Lo que quiero decir es que no es una característica natural del sistema. Se le debe agregar.
AJed
En general, no debe dar como referencia Wikipedia. Acabo de leer ese artículo de Wikipedia: es bastante incompleto y desorganizado; También podría ser confuso.
nbro
5

Una razón por la cual los problemas de consenso son importantes es que son muy simples y son una especie de problemas universales para los sistemas informáticos distribuidos.

Si podemos resolver el consenso en un sistema distribuido asíncrono, podemos usarlo para linealizar acciones en objetos compartidos y obtener linealidad para objetos compartidos.

Para simplificar, ¿en cuántos problemas puede pensar que son más simples que acordar un valor?

El resultado de imposibilidad sobre el consenso en sistemas distribuidos asíncronos (puros) nos dice que no podemos resolver los problemas que queremos resolver en sistemas distribuidos asíncronos (puros) sin algunas "cosas" adicionales. Esto conduce a modelos asíncronos donde podemos resolver el consenso, por ejemplo, algoritmos aleatorios, detectores de fallas, modelos de sincronización parcial, etc.

Esta es también la razón por la cual, en la práctica, los algoritmos que resuelven el consenso como Paxos de Lamport, Chubby de Google, Apache ZooKeeper y más recientemente Raft están en el núcleo de los sistemas distribuidos donde a menudo queremos replicar un estado entre servidores.

Kaveh
fuente
0

Solo agregaría que la naturaleza del cálculo se está distribuyendo cada vez más en la pila: muchas CPU, muchos procesos en una máquina, muchas máquinas conectadas por LAN, muchas LAN conectadas por Internet.

Esto hace que el problema del estado común (distribuido / global) sea primordial: cada algoritmo asume cierto estado y si el cálculo se realiza en más de un lugar, entonces el estado también debe distribuirse.

Los artículos influyentes ( Paxos , y más recientemente Raft ) en este dominio se publicaron después del documento que está citando. Ambos abordan las cuestiones de consenso en presencia de algunos fracasos.

Los errores bizantinos se pueden evitar en sistemas distribuidos utilizando pocos enfoques.

Echa un vistazo a la entrada de Wikipedia sobre la tolerancia bizantina a las fallas .

diginoise
fuente
El resultado de imposibilidad de FLP se aplica incluso en la configuración de la falla más básica (bloqueo), por lo que no estoy seguro de cuál es el punto del párrafo sobre evitar las fallas bizantinas. Tenga en cuenta que si no tenemos fallas, el consenso es bastante fácil: un proceso fijo transmite su valor y cada proceso decide ese valor tan pronto como se recibe.
Kaveh