I tidningen undersöks problemet med Lattice Agreement (LA) i asynkrona system. I LA varje process föreslår ett element e från en förutbestämd lattice, och måste besluta om ett element e i lattice sådan att e ≤ e. Dessutom måste beslut av olika processer vara jämförbara (inga två processer kan besluta två element e och e sådan att (e ≤ e ) (e ≤ e)). Det har visat sig att Generalized LA (dvs. en version av LA som föreslår och beslutar om sekvenser av värden) kan användas för att bygga en replikerad State Machine (RSM) med pendlande uppdateringsoperationer. Den viktigaste fördelen med LA och Generalized LA är att de kan lösas i asynkrona system som är benägna att krascha-misslyckanden (detta är inte fallet med standard Consensus). I den här tidningen antar vi Bysantinska misslyckanden. Vi föreslår Wait Till Safe (WTS) algoritm för LA, och vi visar att dess motståndskraft mot f ≤ (n − 1)/3 Bysantines är optimal. Vi generaliserar sedan WTS erhålla en Generalized LA algoritm, nämligen GWTS. Vi använder GWTS för att bygga en RSM med pendlande uppdateringar. Vår RSM fungerar i asynkrona system och tolererar f ≤ (n-1)/3 skadliga enheter. Alla våra algoritmer använder det minimala antagandet av autentiserade kanaler. När de mer kraftfulla offentliga signaturerna finns tillgängliga diskuterar vi hur vi kan förbättra informationens komplexitet i våra resultat (från kvadratiska till linjära, när f = O(1)). Såvitt vi vet är detta det första dokumentet som föreslår en lösning för Bysantinska LA som fungerar på alla tänkbara lattice, och det är det första arbetet med att föreslå en bysantinska tolerant RSM som bygger på den.
Di Luna m.fl. REF föreslog en lösning för Byzantine LA i asynkrona inställningar, som också tillhandahåller en algoritm för dess generaliserade variant.
Byzantine Generalized Lattice Agreement
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science']}