Abstract-Data replikation teknik möjliggör effektiv och mycket tillgänglig dataåtkomst, vilket ökar och ökar intresset för både den akademiska världen och industrin. Datareplikation introducerar dock problemet med datakonsistens. Moderna kommersiella datareplikationssystem ger ofta svag överensstämmelse för hög tillgänglighet under vissa felscenarier. En viktig svag konsistens är Pipelined-RAM (PRAM)-konsistens. Det gör det möjligt för olika processer att ha olika syn på data. För att avgöra om ett datareplikationssystem verkligen ger PRAM-konsistens studerar vi problemet med att verifiera PRAM-konsistens över läs- och skrivspår (eller VPC, kort sagt). Vi identifierar först fyra varianter av VPC enligt a) om det finns flera delade variabler (eller en enda variabel), och b) om skrivoperationer kan tilldela Duplicerade värden (eller bara unika värden) för varje delad variabel; de fyra varianterna är märkta VPC-SU, VPC-MU, VPC-SD och VPC-MD. För det andra presenterar vi en enkel VPC-MU algoritm, kallad RW-CLOSURE. Den konstruerar en operationsgraf G genom att iterativt lägga till kanter enligt tre regler. Dess tid komplexitet är O(n 5 ), där n är antalet operationer i spåret. För det tredje presenterar vi en förbättrad VPC-MU algoritm, kallad READ-CENTRIC, med tids komplexitet O(n 4). I grund och botten försöker man konstruera operationsgraf G på ett inkrementellt och effektivt sätt. Dess korrekthet är baserad på RW-CLOSURE. Slutligen bevisar vi att VPC-SD (så är VPC-MD) är NP-komplett genom att minska den starkt NP-komplett problem 3-PARTITION till det.
Wei och Al. REF undersökte komplexiteten i att verifiera PRAM-konsistens (även kallad FIFO-konsistens) för en historik.
Verifying PRAM Consistency over Read/Write Traces of Data Replicas
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science']}