Vi överväger problemet med minneskontroll, där en användare vill underhålla en stor databas på en fjärrserver men endast har begränsad lokal lagring. Användaren vill använda den lilla (men betrodda och hemliga) lokala lagringen för att upptäcka fel i den stora (men offentliga och opålitliga) fjärrlagringen. En minneskontroll tar emot från användarbutiken och hämtar verksamheten till den stora databasen. Kontrollen gör sina egna förfrågningar till (otillförlitliga) fjärrlagringen och får svar på dessa förfrågningar. Den använder sedan dessa svar, tillsammans med sitt lilla privata och pålitliga lokala minne, för att förvissa sig om att alla förfrågningar besvarades korrekt, eller för att rapportera fel i fjärrlagringen (det offentliga minnet). En fruktbar forskningslinje undersöker komplexiteten i minneskontroll när det gäller antalet frågor kontrollfrågor per användarförfrågan (query complex) och storleken på det tillförlitliga lokala minnet (space complex). Blum et al., som först formaliserade frågan, skilde mellan online kontroller (som rapporterar fel så snart de inträffar) och offline kontroller (som rapporterar fel endast i slutet av en lång sekvens av operationer). I detta arbete tar vi upp frågan om minneskontroll och frågar hur effektiv minneskontrollen kan vara? För online-kontroller, Blum et al. tillhandahöll en kontroll med logaritmisk frågekomplexitet i n, databasens storlek. Vårt huvudresultat är en lägre gräns: vi visar att för kontroller som kommer åt fjärrlagringen på ett deterministiskt och icke-adaptivt sätt (som alla kända minneskontroller), måste deras frågekomplexitet vara minst  och minst (log n/ log log n). För att klara av detta negativa resultat visar vi hur man byter bort läs- och skrivkomplexet hos onlineminneskontrollörer: för önskad logaritmbas d konstruerar vi en onlinekontroll där antingen läsning eller skrivning är billigt och har frågekomplex O(log d n). Priset för detta är att den andra åtgärden (skriva respektive läsa) har frågekomplex O(d · log d n). Slutligen, om även denna prestanda är oacceptabel, kan offline-minneskontroll vara ett billigt alternativ. Vi tillhandahåller ett schema med O(1) amortized frågekomplexitet, förbättra Blum et al.'s konstruktion, som endast hade sådan prestanda för långa sekvenser av minst n operationer.
Specifikt, i REF är det bevisat att alla icke adaptiva och deterministiska kontroller har läst och skriva frågor komplexitet summering upp till (log n/ log log n) (nödvändigt för sublinjär klient lagring), motivera O (log n) kostnad i vårt system.
How efficient can memory checking be
{'venue': 'In TCC', 'journal': None, 'mag_field_of_study': ['Computer Science']}