Amazon SimpleDB Consistency Enhancements

Amazon SimpleDB Consistency Enhancements.

Abstract
This document outlines the new strong consistency features in SimpleDB - consistent read and conditional put/delete. It also demonstrates how they can be used to program key database application scenarios such as persistent application state, concurrency control, item counter, and conditional update/delete.

3 Phase Commit [3PC]

According to the Wiki - paper "A Formal Model of Crash Recovery in a Distributed System" of Dale Skeen and Michael Stonebraker is main source about 3PC [PDF or PDF].

Paper contains very good analisys and critique of 2PC and definition of 3PC.

There are else some research of thin boundary between Сonsistency and Partition Tolerance (like CAP-Theorem):
"Theorem #2: Rules 1 and 2 are sufficient for designing protocols resilient to a single site failure.
Theorem #3: There exist no protocol using independent recovery that is resilient to arbitrary failures by two sites.
Theorem #4: There exist no protocol resilient to a network partitioning when messages are lost.
Theorem #5: Design Rules 3 and 4 are nesessary and sufficient for making protocols resilient to a partition in a two-site site protocol.
Corollary #6: There exist multisite protocols that are resilient to a simple partition when undeliverable messages are returned to the sender.
Corollary #7: Knowlege of which messages were undelivered at the time the network fails is nesessary and sufficient for recovering from simple partitions.
Theorem #8: There exist no protocol resilient to a multiple partition."

Generalized Isolation Level Definitions

Generalized Isolation Level Definitions.
More recent, more complete, more difficult to follow.

Atul Adya - Microsoft Research
Barbara Liskov - Laboratory for Computer Science, MIT, Cambridge
Patrick O’Neil - Univ. of Massachusetts, Boston

Abstract
Commercial databases support different isolation levels to allow programmers to trade off consistency for a poten tial gain in performance. The isolation levels are defined in the current ANSI standard, but the definitions are ambigu ous and revised definitions proposed to correct the problem are too constrained since they allow only pessimistic (locking) implementations. This paper presents new specifications for the ANSI levels. Our specifications are portable; they apply not only to locking implementations, but also to optimistic and multi-version concurrency control schemes. Furthermore, unlike earlier definitions, our new specifications handle predicates in a correct and flexible manner at all levels.

A Critique of ANSI SQL Isolation Levels

Классика цитирования:
A Critique of ANSI SQL Isolation Levels.
Good, fairly readable discussion of transaction isolation.

Hal Berenson Microsoft Corp.
Phil Bernstein Microsoft Corp.
Jim Gray U.C. Berkeley
Jim Melton Sybase Corp.
Elizabeth O’Neil UMass/Boston
Patrick O'Neil UMass/Boston

Abstract:
ANSI SQL-92 [MS, ANSI] defines Isolation Levels in terms of phenomena: Dirty Reads, Non-Repeatable Reads, and Phantoms. This paper shows that these phenomena and the ANSI SQL definitions fail to properly characterize several popular isolation levels, including the standard locking implementations of the levels covered. Ambiguity in the statement of the phenomena is investigated and a more formal statement is arrived at; in addition new phenomena that better characterize isolation types are introduced. Finally, an important multiversion isolation type, called Snapshot Isolation, is defined.

1 . Introduction
"...which defined Degrees of Consistency in three ways: locking, data-flow graphs, and anomalies."
"The three ANSI phenomena are ambiguous, and even in their loosest interpretations do not exclude some anomalous behavior that may arise in execution histories."
"...lock-based isolation levels have different characteristics than their ANSI equivalents."
"...degrees of consistency defined in 1977 in [GLPT]."
"...Chris Date’s definitions of Cursor Stability..."