Geografiskt distribuerade system förlitar sig ofta på replikerade så småningom konsekventa datalager för att uppnå tillgänglighet och prestanda. För att lösa motstridiga uppdateringar på olika repliker, forskare och utövare har föreslagit specialiserade konsekvent protokoll, som kallas replikerade datatyper, som implementerar objekt som register, räknare, uppsättningar eller listor. Resonemang om replikerade datatyper har dock inte varit i nivå med jämförbart arbete med abstrakta datatyper och samtidiga datatyper, utan specifikationer, korrekturbevis och optimala resultat. För att fylla i denna lucka föreslår vi en ram för att specificera replikerade datatyper med hjälp av relationer över händelser och kontrollera deras implementeringar med hjälp av replikeringsmedvetna simuleringar. Vi tillämpar det på 7 befintliga implementationer av 4 datatyper med icke-triviala konfliktlösningsstrategier och optimeringar (sista-writer-wins register, räknare, multi-värde register och observerad-remove set). Vi presenterar också en ny teknik för att få lägre gränser på det värsta utrymme overhead data typ implementationer och använda den för att bevisa optimalitet av 4 implementationer. Slutligen visar vi hur man specificerar överensstämmelse av replikerade butiker med flera objekt axiomatiskt, i analogi med tidigare arbete på svaga minnesmodeller. Sammantaget ger vårt arbete grundläggande resonemang verktyg för att stödja forskning om replikerade så småningom konsekventa butiker.
Burckhardt m.fl. REF har tidigare föreslagit ett ramverk för att specificera replikerade datatyper (på vilka vi baserar våra listspecifikationer) och visat sig ha lägre gränser på metadata omkostnaderna för flera datatyper.
Replicated data types: specification, verification, optimality
{'venue': "POPL '14", 'journal': None, 'mag_field_of_study': ['Computer Science']}