HIGH AVAILABILITY, RELIABILITY, AND CONSISTENCY OF DATA IN DISTRIBUTED SYSTEMS

摘要

Serializability has been widely accepted as a correctness criterion to achieve data consistency. Most existing concurrency control mechanisms guarantee consistency by preventing serialization errors to occur. Such mechanisms might not be suitable for distributed sysems when the network over which data is accessed is subject to partitioning. We propose a method to perform detection of serialization errors rather than their prevention. Our concurrency control mechanism provides high availability by allowing independent updates in each partition, and then later, during partition merge, easily detects conflicts by checking whether the resulting histories are mutually serializable. The problem of determining if an arbitrary history is serializable is NP-complete. However, we can find efficient algorithms to solve it by taking restrictions on the allowable classes of histories.;If only syntactic information about the transactions is available, i.e., the corresponding read and write sets, then serializability might be the best approach for concurrency control. More sophisticated concurrency mechanisms might be implemented if we can use both transactions' syntactic and semantic information. The addition of semantic information allow us to find semantically serializable histories. Therefore, synchronization mechanisms using both syntactic and semantic information achieve higher concurrency, and enhanced performance, by accepting both serializable and semantically serializable histories, which cannot be attained by traditional concurrency control methods, such as two-phase locking. Semantic information is specified algebraically, and may be applied either to check whether two histories are equivalent or to find if a given history is semantically serializable.