El problema de los generales bizantinos

Sitúese.

Está usted en el campo de batalla arrasado, y el viento ondea sus banderas blasonadas, que amenazan la ciudad rebelde, por fin sitiada. Sin embargo, las torturas a las que ha sometido a los infieles no han minado el espíritu enemigo y ningún prisionero ha revelado la cantidad de hombres que guarda la ciudad amurallada. Usted tiene un ejército numeroso, sí, pero las lineas de comunicación y aprovisionamiento han sido destruidas: no podrá mantener demasiado el sitio sobre la ciudad. Urge tomar una decisión sobre el curso de la batalla y, como general que es, deberá consultar con el resto de mandos. La opciones son pocas: atacar todos a la vez o retirarse.

Pero hay un gran problema: sospecha usted que el enemigo se ha infiltrado en sus filas hasta tal punto que es posible que algunos de sus compañeros generales se encuentren, secretamente, sirviendo al enemigo. ¡Hay traidores entre los generales!. Usted sospecha de un par de ellos pero sólo si es capaz de ponerse de acuerdo con otros generales leales en su acusación podrá desenmascarar a los traidores. No puede usted pensar mucho, sus hombres son bravos pero la lealtad se resiente con el estómago vacío. Sólo podrá derrotar al enemigo si ataca con todas las fuerzas de los generales leales así que... ¿podrá usted descubrir a los traidores?. ¿Será capaz usted de poner de acuerdo a los generales bizantinos?.

El problema de los generales bizantinos fue formulado de esta forma (con menos literatura) por Leslie Lamport^1,2, uno de los grandes de la informática, en 1982. Desde entonces es uno de los clásicos en la teoría de sistemas distribuidos. ¿Y por qué?. Pues veamos.

Piense que en vez de tener usted un conjunto de generales bizantinos tiene usted un conjunto de computadores distribuidos, llevando a cabo una tarea común. Por ejemplo, una transacción bancaria o la monitorización de la ruta de un avión. Eso suena más informático.

Supongamos que uno de los computadores del sistema deja de funcionar. Hace plof y ya está. No responde a los mensajes del resto, ni ofrece resultados: nada. ¿Como podemos saber que ha fallado? Pues muy fácil, como no hace nada ni envía los mensajes que tiene que enviar ni responde a las llamadas, deducimos que ha fallado. Lo más sencillo entonces es reemplazarlo: que otro haga la misma tarea que realizaba. Si un componente 'se muere' de este modo, decimos que ha fallado en modo crash.

Ahora el mismo componente falla, pero en vez de no hacer nada siempre realiza su tarea más tarde de lo que debería. ¿Cómo nos damos cuenta de este fallo?. Pues tan sólo nos es necesario poner en marcha un reloj cuando debería iniciarse. Si, transcurrido el tiempo determinado, el computador o componente no ha ofrecido un resultado, sabemos que está fallando. Y podemos reemplazarlo por otro, como antes. En este caso decimos que el componente falla en modo performance.

Un pasito más. Supongamos que un elemento ofrece resultados dentro del tiempo establecido pero... estos resultados son siempre incorrectos. Aquí se complica la cosa. ¿Cómo sabemos si falla?. Podemos, por ejemplo, poner dos procesadores a hacer la misma tarea y comparar los resultados pero aún así si estos no concuerdan, ¿cómo saber cuáles son los buenos y cuales no?. En este caso necesitamos tres componentes para tolerar el fallo de uno. Y, en general, 2n+1 para tolerar n fallos. Estos fallos se llaman response. Y los sistemas con tres componentes y un comparador se llaman TMR (triple modular redundancy).

¿Se han fijado cómo cada vez necesitamos más cosas para detectar el fallo?

Y ahora vamos a lo bueno. Supongamos que un componente tiene un comportamiento errático y que, a veces ofrece una respuesta correcta y a veces no. Supongamos que, en las votaciones para detectar la respuesta correcta, este computador acusa a otros de ser los erróneos: a uno le dice una cosa, a otro otra distinta. Actúa como un traidor. Como un traidor bizantino.

Está usted de nuevo en el campo de batalla. Y ya tiene su decisión, atacar o retirarse, que debe transmitir al resto de generales. Los generales leales no se equivocarán, y si creen que atacar es la mejor opción, arrasarán al enemigo. Sin embargo puede que los traidores consigan que decidamos retirarnos. Por otro lado, aunque una mayoría de generales leales haya decidido no atacar, es posible que con el voto de los traidores se fuerce el asalto, cayendo en una trampa mortal.

Usted razona: si sólo hubiera tres generales y uno fuera el traidor... ¿podríamos ponernos de acuerdo la mayoría? Supongamos que yo -Apocapes- envío a ambos la orden de atacar. Los generales Belisarius y Comentiolus reciben mi orden, bien. Y sin embargo, el traidor Belisarius informa a Comentiolus de que mi orden ha sido la de retirada. ¿Que pensará Comentiolus? Pues que, o bien Belisarius es el traidor, como de hecho sucede... ¡o bien que el traidor soy yo, el insigne general Apocapes!. Las dos situaciones serían indistinguibles a los ojos de Comentiolus.

Así que, a pesar de ser mayoría los generales leales (de 2 a 1), no podremos llegar nunca a un acuerdo, pues no sabremos de quien fiarnos. Si dispusiéramos de cartas firmadas... podría enviar cada una de ellas al resto de generales y luego estos intercambiar las mismas. Sin embargo cada general sólo puede controlar lo que transmite, no lo que intercambia el resto.

Entonces ¿y si somos cuatro y uno infiel?. Entonces sí que será posible, puesto que Droctulf, el cuarto general, podrá confirmar que yo di la orden de atacar. ¿Será posible que con más del triple de generales leales podamos acordar una solución?

Por supuesto, la suposición a usted no le vale. Necesita la prueba matemática de cuántos generales son necesarios para llegar a un acuerdo con t generales traidores infiltrados. Pero eso aquí no aparecerá: digamos que simplemente imagina grupos de 3t o menos generales generales (albaneses) que alcanzan el acuerdo: consigue reducir el problema al de los tres generales encontrando por tanto una contradicción. Se requieren 3t + 1 generales leales para acordar una solución.

Las banderas se hinchen con renovada fuerza en el campamento. Los generales que rodean la ciudad son 8 y, si el Imperio Bizantino aún conserva parte de su gloria, los traidores serán dos de ellos. Ahora sabe usted que sin duda podrán alcanzar la mejor decisión.

¿Y qué tiene que ver esto con la informática?. Pues mucho. Si usted no es capaz de evitar los fallos bizantinos en sus programas o componentes que actúan de manera distribuida, sepa que cualquier sistema de decisión requerirá de al menos MAS DEL TRIPLE de componentes que actúen correctamente que los que no³.

Y eso es vital en Tolerancia a Fallos: los sistemas están diseñados para que cualquier tipo de fallo pueda convertirse en uno tipo crash. Aunque se necesite aumentar la circuitería o software de detección, los fallos crash (u omission) -semántica débil de fallo- son por lo general más fáciles de tratar.

Y por eso se le suele dar muerte a los traidores. Es la solución mas ingenieril.

¹ El problema de los generales es más antiguo, pero la generalización de Lamport es la más conocida.
² ¿Sabían que Leslie Lamport también creó LaTeX (Lamport TeX)?
³ Siempre que las comunicaciones sean como las descritas, esto es, que un miembro no puede garantizar que e estado que de él transmiten los otros es cierto.

LESLIE LAMPORT, ROBERT SHOSTAK, and MARSHALL PEASE. The Byzantine Generals Problem. ACM Transactions on Programming Languages and Systems, Vol. 4, No. 3, July 1982, pp 382-401. (enlace)
Lista de Generales Bizantinos

Posts relacionados

El trabajo de Aitor Menta (sobre tolerancia a fallos)
Códigos correctores de errores