Distribuerade protokoll som Paxos spelar en viktig roll i många datorsystem. Därför kan en bugg i ett distribuerat protokoll ha enorma effekter. Följaktligen har stora ansträngningar gjorts för att kontrollera sådana protokoll. Att kontrollera invarianter av sådana protokoll är dock obeslutbart och svårt i praktiken, eftersom det kräver resonemang om ett obegränsat antal noder och meddelanden. Dessutom omfattar protokollåtgärder och invarianter både kvantifier-alternationer och högre ordningsbegrepp såsom fastställda kardinaler och aritmetiska. Detta dokument utgör ett steg mot automatisk kontroll av sådana protokoll. Vi siktar på en teknik som kan verifiera korrekta protokoll och identifiera fel i felaktiga protokoll. I detta syfte utvecklar vi en metod för deduktiv verifiering baserad på effektivt propositionslogik (EBR)-ett decibelt fragment av första ordningens logik (även känd som Bernays-Schönfinkel-Ramsey klassen). Förutom decisionability har EPR också den finita modellen egenskap, vilket gör det möjligt att visa överträdelser som finita strukturer som är intuitiva för användare. Vår metod innebär att modellera protokoll med hjälp av allmän (otolkad) första ordningen logik, och sedan systematiskt omvandla modellen för att få en modell och en induktiv invariant som är decidable att kontrollera. Omvandlingsstegen kontrolleras också mekaniskt, vilket säkerställer att metoden är sund. Vi har använt vår metodik för att verifiera säkerheten hos Paxos, och flera av dess varianter, inklusive Multi-Paxos, Vertikal Paxos, Fast Paxos, Flexible Paxos och Stopable Paxos. Såvitt vi vet är detta arbete det första att verifiera dessa protokoll med hjälp av en decledable logik, och den första formella verifieringen av Vertical Paxos, Fast Paxos och Stopable Paxos.
Det har använts för att verifiera nätverksprotokoll såsom ledarval i ringtopologier och PAXOS-protokollet REF.
Paxos made EPR: decidable reasoning about distributed protocols
{'venue': 'PACMPL', 'journal': None, 'mag_field_of_study': ['Computer Science']}