Bysantinska generalsproblemet

Från Wikipedia
Hoppa till: navigering, sök

Det bysantinska generalsproblemet som introducerades för mer än 20 år sedan bygger på ett klassiskt problem tillämpat på feltoleranta datorsystem. Definitionen av bysantinska fel och hur man skall hantera dem presenterades i en artikel av den amerikanske datavetaren och matematikern Leslie Lamport och hans medarbetare. Lamport beskriver ett scenario där en grupp bysantinska generaler, med sina arméer, har omringat en fientlig styrka. Efter att ha observerat fienden från sin position måste generalerna skaffa sig en gemensam ståndpunkt via meddelanden för att därefter bestämma sig för att attackera eller retirera. Om alla generalerna attackerar samtidigt besegras fienden men om en eller flera av generalerna får motsägelsefull information och därför inte attackerar, eller attackerar vid fel tidpunkt, förloras striden och generalerna och deras soldater måste kapitulera. Problemet är att en eller flera av generalerna eller deras kurirer kan vara förrädare som vill förstöra möjligheten till ett lyckat anfall.

Flera tekniker och algoritmer har föreslagits för att förbättra pålitligheten i generalernas meddelandekedja, det vill säga samma problem som man har inom distribuerade inbyggda datorsystem, främst för säkerhetskritiska, så kallade by-wire tillämpningar inom flyg- och fordonsindustrin. Men liknande fel är fortfarande en utmaning för forskare och utvecklare av datorsystem med höga pålitlighetskrav. Det finns många missuppfattningar om dessa fel, till exempel vad som gör ett datorsystem sårbart, felens egenskaper och hur de uppträder.

Den generella lösningen är att det behövs fyra oberoende observatörer eller generaler för att kunna identifiera en godtycklig förrädare, sju för att klara två förrädare.

Referenser[redigera | redigera wikitext]

H. Sivencrona, doktorsavhandling. Ingen copyright åberopas, texten finns också på [1]

L. Lamport, R. Shostak, and M. Pease, The Byzantine Generals Problem, ACM Trans. Programming Languages and Systems, Vol. 4, No. 3, July 1982, pp. 382-401.