bysantinska generalsproblemet

i datorvetenskap: utmaningen att få ett it-system att fatta bästa möjliga beslut, som måste verkställas av alla delar av systemet, när det är tänkbart att någon del av systemet lämnar felaktig information eller inte kommunicerar alls. Eller att olika delar av systemet lämnar olika information om samma sak. Problemet formulerades först med tanke på krångel i it‑system. Det bysantinska generalsproblemet är också relevant för så kallade konsensusalgoritmer, alltså algoritmer som fastställer att en viss transaktion eller annan åtgärd är giltig om den godkänns av ett visst antal noder, eller alla, i ett nätverk. – Det bysantiska generalsproblemet har tre delar:

  1. – att få alla delar att medverka till ett välgrundat gemensamt beslut;
  2. – att förhindra att någon del av systemet skickar felaktig eller vilseledande information till andra delar av systemet;
  3. – att hantera eventuell brist på kommunikation (att någon del av systemet inte deltar i arbetet med att lösa problemet).

– Det bysantinska generalsproblemet har namn efter ett scenario där ett antal bysantinska generaler belägrar en stad. De måste komma överens om ifall de ska anfalla staden eller låta bli. Ett anfall kan bli framgångsrikt bara om alla generalerna låter sina arméer anfalla samtidigt (konsensus). Om några generaler anfaller men andra låter bli slutar det med nederlag. Generalerna kan inte träffas, utan skickar budbärare till varandra. Det är nödvändigt att alla generalerna talar om för varandra om de vill anfalla eller avstå. Beslut fattas först när alla har jämfört sina bedömningar med varandra. Man måste ha kommunikation med alla generalerna, och man måste gardera sig mot förräderi: som att någon av generalerna skickar ett besked till några av generalerna och ett annat besked till andra. Man måste också gardera sig mot att budbärarna fifflar med beskeden. – En ingående analys från 1982 av det bysantinska generalsproblemet, författad av Leslie Lamport, Robert Shostak och Marshall Pease, kan laddas ner här. – Kallas också för bysantinska generalerna, på engelska the Byzantine generals problem. – Varför problemet har uppkallats efter just bysantinska generaler är okänt.

  • Byzantine fault – bysantinskt fel – är ett fel som ter sig olika för olika komponenter i ett datorsystem. Det är därför ett problem för systemet att avgöra vad det ska göra åt felet, eller ifall det verkligen är ett fel;
  • Byzantine fault tolerance – bysantinsk feltolerans – system för feltolerans som kan hantera bysantinska fel (se ovan);
  • Byzantine failure – bysantinskt funktionsfel – funktionsfel (det att datorsystemet helt eller delvis slutar att fungera) som orsakas av ett bysantinskt fel.

[datorvetenskap] [fel] [ändrad 9 oktober 2018]

Dagens ord: 2018-02-02