Byzantinske fejltolerance

Byzantinske fejltolerance er en sub-felt for fejltolerance forskning inspireret af de byzantinske generaler 'problem, som er en generaliseret version af de to generaler' Problem.

Formålet med byzantinske fejltolerance er at være i stand til at forsvare sig mod byzantinske fejl, hvor komponenter i et system mislykkes i arbitrære måder. Korrekt fungerende komponenter i en byzantinsk fejltolerant system vil være i stand til korrekt at give systemets tjeneste forudsat der ikke er for mange byzantinske defekte komponenter.

Fejltilstande

En byzantinsk fejl er en vilkårlig fejl, der opstår under udførelsen af ​​en algoritme, som et distribueret system. Det omfatter både udeladelse fejl og provision fiaskoer. Når en byzantinsk der er opstået, kan systemet reagere på nogen uforudsigelig måde, medmindre den er designet til at have byzantinsk fejltolerance.

For eksempel, hvis outputtet fra én funktion er input for en anden, kan derefter små afrundingsfejl i den første funktion producere meget større fejl i den anden. Hvis den anden funktion blev fodret ind i en tredje, kan problemet vokse endnu større, indtil værdierne produceret er værdiløse. Et andet eksempel er i kompilere kildekode. En mindre syntaktiske fejl tidligt i koden kan producere store antal af opfattede fejl senere, da parseren af ​​compileren kommer ud af fase med den leksikale og syntaktiske information i kilden programmet. Sådanne fejl har bragt ned store internettjenester. For eksempel, Amazon S3 i 2008 blev bragt ned i flere timer, når en enkelt-bit hardware fejl opformeret gennem systemet.

I en byzantinsk fejltolerant algoritme, er skridt taget af processer, de logiske abstraktioner, der repræsenterer stien udførelse af algoritmer. En defekt proces er en, på et tidspunkt udviser nogen af ​​de ovennævnte fejl. En proces, der ikke er defekt er korrekt.

De byzantinske fiasko antagelse modeller virkelige verden miljøer, hvor computere og netværk kan opføre sig på uventede måder på grund af hardwarefejl, overbelastning af nettet og frakobling samt ondsindede angreb. Byzantinske fejl-tolerante algoritmer skal håndtere sådanne fejl og stadig tilfredstille specifikationerne i de problemer, de er designet til at løse. Sådanne algoritmer er almindeligt karakteriseret ved deres modstandsdygtighed t, antallet af fejlbehæftede processer, hvormed en algoritme kan klare.

Mange klassiske aftale problemer, såsom de byzantinske generaler 'Problem, har ingen løsning, medmindre n ≥ 3t + 1, hvor n er antallet af processer i systemet, og t er antallet af forrædere. Med andre ord kan algoritmen sikre korrekt funktion, hvis færre end en tredjedel af processerne er defekte.

Origin

Byzantinske refererer til de byzantinske generaler 'problem, en aftale, problem, hvor generaler i Det Byzantinske Rige hær enstemmigt skal beslutte, om at angribe nogle fjendens hær. Problemet kompliceres af den geografiske adskillelse af generalerne, der skal kommunikere ved at sende budbringere til hinanden, og ved tilstedeværelsen af ​​forrædere blandt generalerne. Disse forrædere kan handle vilkårligt for at opnå følgende mål: narre nogle generaler i at angribe; tvinge en beslutning, som ikke er i overensstemmelse med generalernes begær, f.eks tvinge et angreb, når der ikke generelt ønsker at angribe; eller forvirrende nogle generaler til det punkt, at de er i stand til at gøre op deres sind. Hvis forræderne lykkes i nogen af ​​disse mål deraf følgende angreb er dømt, da kun en samordnet indsats kan resultere i sejr.

Byzantinske fejltolerance kan opnås, hvis de loyale generaler har en enstemmig aftale om deres strategi. Bemærk, at hvis kilden generelt er korrekt, skal alle loyale generaler enige om denne værdi; ellers valg af strategi aftalt er irrelevant.

Tidlige løsninger

Flere løsninger blev oprindeligt beskrevet af Lamport, Shostak, og Pease i 1982. De begyndte med at konstatere, at de generaler 'problem kan reduceres til løsning af en "Commander og løjtnanter" problem, hvor Loyale løjtnanter alle skal handle i fællesskab, og at deres indsats skal svare til, hvad Commander bestilt i tilfælde af, at den øverstbefalende er Loyal. Groft sagt de generaler stemme ved at behandle hinandens ordrer som stemmer.

  • En løsning anser scenarier, hvor meddelelser kan smedede, men som vil være byzantinsk-fejltolerant, så længe antallet af forræderiske generaler ikke lig eller bedre end en tredjedel. Umuligheden af ​​at håndtere en tredjedel eller flere forrædere i sidste ende reducerer til at bevise, at 1 Commander + 2 løjtnanter problemet ikke kan løses, hvis Commander er forræderiske. Årsagen er, hvis vi har tre chefer, A, B, og C, og A er forræderen: når A fortæller B til at angribe og C at trække sig tilbage, og B og C sende meddelelser til hinanden, og sender en budskab, hverken B heller C kan finde ud af, hvem der er forræder, da det er ikke nødvendigvis en anden kommandant kunne have forfalsket beskeden angiveligt fra A. Det kan vises, at hvis n er antallet af generaler i alt, og t er antallet af forrædere i at n, så er der løsninger på problemet, når n & gt; 3t.
  • En anden løsning kræver forfalskningssikkert underskrifter, men fastholder byzantinsk fejltolerance i overværelse af et vilkårligt antal forræderiske generaler.
  • Også fremlagt er en variation på de første to løsninger, der giver mulighed byzantinsk-fejltolerant adfærd i nogle situationer, hvor ikke alle generaler kan kommunikere direkte med hinanden.

Praktisk byzantinske fejltolerance

Byzantinske fejltolerant replikation protokoller blev længe anset for dyrt at være praktisk. Så i 1999, Miguel Castro og Barbara Liskov introducerede "Praktiske byzantinske fejltolerance" algoritme, som giver høj ydeevne byzantinske tilstand maskine replikation, behandler tusinder af forespørgsler per sekund med sub-millisekund stigninger i latenstid.

PBFT udløste en renæssance i BFT replikation forskning, med protokoller som Q / U, HQ, Zyzzyva og abstracts arbejder på at sænke omkostningerne og forbedre ydeevnen og protokoller som Aardvark og RBFT arbejder på at forbedre robustheden.

Upright er et open source-bibliotek til at konstruere tjenester, der tåler både nedbrud og byzantinske adfærd, der indeholder mange af disse protokoller 'innovationer.

Et eksempel på BFT i brug er Bitcoin, et peer-to-peer digitale valuta system. Den Bitcoin-netværket arbejder parallelt for at generere en kæde af Hashcash stil proof-of-arbejde. Proof-of-arbejde kæden er nøglen til at overvinde byzantinske fejl og for at nå frem til en sammenhængende global visning af systemets tilstand.

Udover PBFT og Upright, er der også BFT-smart bibliotek, en højtydende byzantinske fejltolerant tilstandsmaskine replikation bibliotek udviklet i Java. Dette bibliotek implementerer en protokol meget lig PBFT s, plus supplerende protokoller, der tilbyder state overførsel og on-the-fly omstrukturering af værter. BFT-SMART er den seneste indsats for at gennemføre statsmaskine replikation, stadig aktivt vedligeholdt.

Archistar udnytter en slank BFT lag for kommunikation. Det prototyper en sikker multi-sky lagersystem inden Java hjælp GPLv2. Fokus ligger på enkelhed og læsbarhed, den sigter mod at være fundamentet for yderligere forskningsprojekter.

  0   0

Kommentarer - 0

Ingen kommentar

Tilføj en kommentar

smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile
Tegn tilbage: 3000
captcha