El problema dels generals bizantins és un experiment mental per a plantejar, d'una forma metafòrica, el problema que es dona entre un conjunt de sistemes informàtics que tenen un objectiu comú. Deuen trobar un pla d'acció comuna a partir d'una estructura jeràrquica, a on un dels sistemes que té major ranc proporciona una orde a partir de la qual el restant de sistemes té que operar (fixar la seua decisió). Ademés és possible que algun d'ells no siga fiable i proveïxca informació falsa de forma intencionada.[1][2]
Supongam un escenari de guerra en el que tenim un grup de m generals bizantino que estan sitiant una ciutat des de distints llocs i tenen que posar-se d'acort per a atacar o retirar-se de forma coordinada. Entre els generals hi ha solament un que pot cursar l'orde per ser el comandant. El restant es diu que són tinents.
Els tinents es comuniquen entre ells quan reben l'orde del comandant i les dos possibles órdens del comandant són "atacar" i "retirar-se".
Un o més dels generals pot ser un traïdor (al restant se'ls crida lleals), per lo que el seu objectiu és conseguir que tots els generals lleals no es posen d'acort. Per a això poden oferir informació errònea. Per eixemple, si el comandant és el traïdor, podria manar órdens contradictòries als distints tinents. Si el tinent és un traïdor podria indicar-los a atres tinents, en la finalitat de confondre'ls i que cregueren que el traïdor és el comandant, que el comandant els va enviar l'orde contrària a la que realment els va enviar.
Per a resoldre el problema tenim que buscar algoritmes que nos permeten conseguir algun dels següents objectius:[3]
Tots els tinents lleals prenen la mateixa decisió.
Si el comandant és lleal, llavors tots els tinents lleals realisen l'orde que ell va decidir.
Normalment per a aplegar a una solució se solen fer les següents condicions adicionals:[2]
Cada mensage que s'envia aplega correctament.
Cada receptor d'un mensage coneix quí ho envia.
L'absència de mensage pot ser detectada.
Davant l'absència de mensage es té una orde per defecte. Esta condició és per a evitar el problema de que el comandant siga un traïdor i no envie órdens.
L'estratègia es basa, en la finalitat de detectar si el comandant és el traïdor, que els tinents es reenvíen entre sí l'informació que el comandant els ha manat. Si el tinent és lleal l'informació que transmetrà el tinent serà la que li va enviar el comandant. La conseqüència d'usar mensages orals (no firmats) és que un general traïdor pot dir que el comandant li ha manat certa informació quan no és aixina.
Analisem el cas en el que tenim tres generals (m=3).
Supongam que el comandant és un traïdor. Si el comandant envia una orde distinta a cada tinent llavors hi haurà un tinent que no sàpia qué acció realisar:
Supongam que un tinent és el traïdor. Llavors est retransmet a l'un atre tinent informació distinta a la que va rebre del comandant. Per tant l'atre tinent no sabrà qué acció realisar:
La conclusió és que no existix solució que garantise que es complixquen les condicions del problema si es permet que en tres generals un siga un traïdor. Açò es deu a que no hi ha suficients generals per a formar una opinió consensuada.
Generalisant a m generals es pot dir que si tenim t traïdors necessitem que m siga a lo manco 3t+1.
A l'algoritme generalisat se li crida OM(m) (a on les sigles OM vénen de l'anglés Oral Messages) i ve descrit per usar la següent funció de majoria:
Tornar el valor de v que siga majoria entre
A on el valor de és l'orde manada des dels distints generals al general al que estem evaluant la seua decisió.
Mensages firmats i tots es poden comunicar en tots
En este escenari els mensages van firmats (es tracta de mensages escrits). En anar firmats no són modificables i per tant els traïdors no poden modificar-los i dir que provenen del comandant. En esta situació és possible resoldre el problema en només tres generals i un d'ells traïdor.
L'algoritme d'este tipo de problemes es diu SM(m) (a on SM ve de l'anglés Signed Messages) i és el següent:
Primer el comandant envia una orde firmada a tots els tinents. Cada volta que un tinent rep un mensage firmat ho guarda, fa una còpia, la firma i la reenvía a tots els tinents que no venien en la firma del document. Segons este algoritme els generals no rebran més mensages quan tinguen totes les possibles combinacions. Una volta rebudes, cada nodo pren la decisió basant-se en l'orde transmesa per la majoria.
En este escenari els comandants traïdors són descoberts immediatament ya que han firmat órdens contradictòries.
Si falta algun dels camins de comunicació les coses es compliquen. Vejam els requeriments tant quan hi ha mensages orals com a mensages firmats.
En mensage orals l'algoritme OM(m) solament funciona baix la condició de que el grafo de camins possibles entre generals siga 3m-regular (cada nodo té a lo manco 3m veïns), lo que implica 3m+1 nodos (generals). A esta versió de l'algoritme se li crida OM(m,p), a on p és el número de veïns.
Per a mensages firmats l'única condició és que tots els generals lleals estiguen conectats, per a que aixina els traïdors no puguen bloquejar-li i evitar que li passen o passe l'orde firmada.
Archivat el 16 de juny de 2017 archivat en Wayback Machine.. Marcelo Valdivia Lagos. 04/04/2013
↑ «The Byzantine Generals Problem» (en en) (pdf). Universitat de Basilea. Archivat des d'el original, el 3 d'octubre de 2016. Consultat el 19 de novembre de 2019. «This paper discusses what happens if computer systems must find a common pla of action,and it is possible that some of them llaure faulty and provide bad input. It uses the metaphor ofByzantine armies around an enemy city, who must together decidix if they should "attack" or"retreat", while being able to communicate only by messenger, and not knowing if some ofthem might be traitors»
