Golab, Wojciech; Li, Xiaozhou; Shah, Mehul A.
HP Laboratories
HPL-2011-6
Schlüsselbegriff (e): Datenkonsistenz, algorightms, Schlüssel-Wert-Speicher
Abstract: Motiviert durch die zunehmende Beliebtheit der schließlich konsequente Schlüssel-Wert-Speicher, wie ein kommerzieller Dienst, wenden wir uns zwei wichtige Probleme im Zusammenhang mit der Konsistenz Eigenschaften in einer Geschichte von Operationen auf einer Lese / Schreib-Register (dh, die Startzeit, Endzeit, Argument und die Reaktion eines jeden Betrieb). Zunächst betrachten wir, wie man eine Konsistenz Verletzung sobald man passiert, zu erkennen. Zu diesem Zweck formulieren wir eine Spezifikation für Online-Prüfung Algorithmen, und wir stellen solche Algorithmen für mehrere bekannte Konsistenz Eigenschaften. Zweitens sehen wir, wie die Schwere der Verletzungen zu quantifizieren, wenn eine Geschichte gefunden, um die Konsistenz Verstöße enthalten. Wir untersuchen zwei Größen: zum einen die Abgestandenheit der liest, und das andere ist die Gemeinsamkeit der Verletzungen. Für Abgestandenheit wir weiter zu prüfen, zeitbasierte Abgestandenheit und Betrieb-count-basierte Abgestandenheit. Wir präsentieren effiziente Algorithmen, dass diese Mengen zu berechnen. Wir glauben, dass die Lösung dieser Probleme hilft sowohl Schlüssel-Wert-Speicher-Anbieter und Nutzer zu ergreifen Datenkonsistenz als ein wichtiger Aspekt von Schlüssel-Wert-Speicher-Angebote.
26 Seiten
Zusätzliche Publication Information: Um veröffentlicht und präsentiert auf PODC 2011, San Jose, June 6-8, 2011.
Externe Posting Datum: 6. Juni 2011 [Fulltext]. Zugelassen für External Publication
Interne Posting Datum: 6. Juni 2011 [Fulltext]
No comments:
Post a Comment