Abstrakt. Samförstånd är det paradigma problemet i feltolerant distribuerad dator: det kräver nätverksnoder som kommunicerar genom meddelande passerar att komma överens om gemensamt värde även i närvaro av (benign eller skadliga) fel. Flera algoritmer för att lösa samförstånd existerar, men få av dem har verifierats rigoröst, mycket mindre formellt. Heard-Of-modellen föreslår ett enkelt, enande ramverk för att definiera distribuerade algoritmer i närvaro av kommunikationsfel. Algoritmer fortsätter i kommunikationsstängda rundor, och antaganden om de fel som tolereras av algoritmen anges abstrakt i form av kommunikationsprinciper. Utvidga tidigare arbete med fall av godartade fel, vår strategi bygger på det faktum att egenskaper som Consensus kan verifieras över en grovkornig, rund-baserad representation av avrättningar. Vi har kodat Heard-Of-modellen i den interaktiva bevisassistenten Isabelle/HOL och har använt denna kodning för att formellt verifiera tre Consensus-algoritmer baserade på synkrona och asynkrona antaganden. Våra bevis ger några nya insikter om algoritmernas korrekthet, särskilt när det gäller övergående fel.
En annan modell för distribuerade algoritmer har kodats i den interaktiva bevisassistenten Isabelle/HOL, och används för att verifiera flera konsensusalgoritmer REF.
Formal Verification of Consensus Algorithms Tolerating Malicious Faults
{'venue': 'SSS', 'journal': None, 'mag_field_of_study': ['Computer Science']}