Bysantinska generalsproblemet

Det bysantinska generalsproblemet, som introducerades på 1980-talet, bygger på ett klassiskt problem tillämpat på feltoleranta datorsystem.

Definitionen av bysantinska fel och hur man skall hantera dem presenterades 1982 i en artikel^[1] 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

^ Leslie Lamport, Robert Shostak, Marshall Pease (1982). ”The Byzantine Generals Problem”. ACM Transactions on Programming Languages and Systems (Baltimore: ACM - Association for Computing Machinery) 4 (3): sid. 382-401. ISSN 0164-0925. https://lamport.azurewebsites.net/pubs/byz.pdf.

Källor

Sivencrona, Håkan (2004) (på engelska). On the design and validation of fault containment regions in distributed communication systems. Doktorsavhandlingar vid Chalmers tekniska högskola. Ny serie, 0346-718X ; 2060Technical report. D / School of Computer Science and Engineering, Chalmers University of Technology, 1651-4971 ; 23. Göteborg: Chalmers tekniska högsk. Libris 9352118. ISBN 9172913789. https://web.archive.org/web/20070928031911/http://www.safari.vr.se/servlet/GetDoc?meta_id=3510&category=3

[1] Leslie Lamport, Robert Shostak, Marshall Pease (1982). ”The Byzantine Generals Problem”. ACM Transactions on Programming Languages and Systems (Baltimore: ACM - Association for Computing Machinery) 4 (3): sid. 382-401. ISSN 0164-0925. https://lamport.azurewebsites.net/pubs/byz.pdf.

[1]