Den probabilistiska I/O Automatonmodellen av [31] används som grund för en formell presentation och bevis på Aspnes och Herlihys randomiserade konsensusalgoritm. Algoritmen garanterar terminering inom förväntad polynomtid. Aspnes-Herlihy algoritmen är en ganska komplex algoritm. Processer rör sig genom en följd av asynkrona rundor, försöker komma överens vid varje omgång. Vid varje omgång, avtalet försök innebär en distribuerad slumpmässig promenad. Algoritmen är svår att analysera på grund av dess användning av icke-triviala resultat av sannolikhetsteori (specifikt, slumpmässig gångteori som är baserad på oändligt många mynt flips snarare än på finitly många mynt flips), på grund av dess komplexa inställning, inklusive asynkrony och både icke-deterministiska och probabilistiska val, och på grund av samspelet mellan flera olika underprotokoll. Vi formaliserar Aspnes-Herlihy algoritmen med probabilistisk I/O automata. Genom att göra det bryter vi formellt ner det i tre underprotokoll: en för att genomföra överenskommelsen försök, en för att genomföra slumpmässiga promenader, och en för att genomföra en delad räknare som behövs av slumpmässiga promenader. Egenskaper hos alla tre delprotokoll bevisas separat, och kombineras med allmänna resultat om automatisk sammansättning. Det visar sig att det mesta av arbetet handlar om att bevisa icke-probabilistiska egenskaper (invarianter, simuleringskartläggningar, icke-probabilistiska förloppsegenskaper osv.). Det probabilistiska resonemanget är isolerat för några få små delar av beviset. Uppgiften att utföra detta bevis har lett oss att utveckla flera allmänna bevistekniker för probabilistiska I/O automata. Dessa inkluderar sätt att kombinera förväntningar på olika komplexa åtgärder, att komponera förväntade komplexa egenskaper, att konvertera probabilistiska påståenden till deterministiska påståenden, att använda abstraktion kartläggningar för att bevisa probabilistiska egenskaper, och att tillämpa slumpmässiga gångteori i en distribuerad beräkningsmiljö. Vi använder alla dessa tekniker för att analysera algoritmens förväntade komplexitet.
Ett antal kompositionssäkra tekniker utvecklades också och, i REF, tillämpades på den manuella verifieringen av Aspnes och Herlihys randomiserade konsensusalgoritm.
Verification of the randomized consensus algorithm of Aspnes and Herlihy: a case study
{'venue': 'Distributed Computing', 'journal': 'Distributed Computing', 'mag_field_of_study': ['Computer Science', 'Engineering']}