Providing a shared memory abstraction in distributed systems is a powerful tool that can simplify the design and implementation of software systems for networked platforms. This enables the system designers to work with abstract readable and writable objects without the need to deal with the complexity and dynamism of the underlying platform. The key property of shared memory implementations is the consistency guarantee that it provides under concurrent access to the shared objects. The most intuitive memory consistency model is atomicity because of its equivalence with a memory system where accesses occur serially, one at a time. Emulations of shared atomic memory in distributed systems is an active area of research and development. The problem proves to be challenging, and especially so in distributed message passing settings with unreliable components, as is often the case in networked systems. We present several approaches to implementing shared memory services with the help of replication on top of message-passing distributed platforms subject to a variety of perturbations in the computing medium.

Cloud storage services and NoSQL systems typically offer only "Eventual Consistency", a rather weak guarantee covering a broad range of potential data consistency behavior. The degree of actual (in-)consistency, however, is unknown. This work presents novel solutions for determining the degree of (in-)consistency via simulation and benchmarking, as well as the necessary means to resolve inconsistencies leveraging this information.

Cloud storage services and NoSQL systems typically offer only ""Eventual Consistency"", a rather weak guarantee covering a broad range of potential data consistency behavior. The degree of actual (in-)consistency, however, is unknown. This work presents novel solutions for determining the degree of (in-)consistency via simulation and benchmarking, as well as the necessary means to resolve inconsistencies leveraging this information. This work was published by Saint Philip Street Press pursuant to a Creative Commons license permitting commercial use. All rights not granted by the work's license are retained by the author or authors.

Distributed storage systems are constrained by the finite speed of propagation of information. The CAP (which stands for consistency, availability, and partition tolerance) theorem states that in the presence of network partitions, a choice has to be made in between availability and consistency. However, even in the absence of failures, a trade-off between consistency and latency of operations (reads and writes) exists. Eventually consistent storage systems often sacrifice consistency for high availability and low latencies. One way to achieve fine-tuning in the consistency-latency trade-off space is to inject artificial delays to each storage operation. This thesis describes an adaptive tuning framework that is able to calculate the values of artificial delay to be injected to each storage operation to meet a specific target consistency. The framework is able to adapt nimbly to environmental changes in the storage system to maintain target consistency levels. It consists of a feedback loop which uses a technique called spectral shifting at each iteration to calculate the target value of artificial delay from a history of operations. The tuning framework is able to converge to the target value of artificial delay much faster than the state-of-art solution. This thesis also presents a probabilistic analysis of inconsistencies in eventually consistent distributed storage systems operating under weak (read one, write one) consistency settings. The analysis takes into account symmetrical (same for reads and writes) artificial delays which enable consistency-latency tuning. A mathematical formula for the percentage of inconsistent operations is derived from other environmental parameters pertaining to the storage system. The formula's predictions for the proportion of inconsistent operations match observations of the same from a stochastic simulator of the storage system running 10^6 operations (per experiment), and from a widely used key-value store (Apache Cassandra) closely.

Modern distributed storage systems are emerging as the primary choice for storing massive amounts of critical data that we generate today. A central goal of these systems is to ensure data durability, i.e., these systems must keep user data safe under all scenarios. To achieve high levels of durability, most modern systems store redundant copies of data on many machines. When a client wishes to update the data, the distributed system takes a set of actions to update these redundant copies, which we refer to as the system's durability model. At one end of the durability model spectrum, data is immediately replicated and persisted on many or all servers. While this immediate durability model offers strong guarantees, it suffers from poor performance. At the other end, data is only lazily replicated and persisted, eventually making it durable; this approach provides excellent performance but poor durability guarantees. The choice of durability model also influences what consistency models can be realized by the system. While immediate durability enables strong consistency, only weaker models can be realized upon eventual durability. Thus, in this dissertation, we seek to answer the following question: is it possible for a durability model to enable strong consistency guarantees, yet also deliver high performance? In the first part of this dissertation, we study the behavior of eight popular modern distributed systems and analyze whether they ensure data durability when the storage devices on the replicas fail partially, i.e., sometimes return corrupted data or errors. Our study reveals that redundancy does not provide fault tolerance; a single storage fault can result in catastrophic outcomes such as user-visible data loss, unavailability, and spread of corruption. In the second part, to address the fundamental tradeoff between consistency and performance, we propose consistency-aware durability or CAD, a new way to achieving durability in distributed systems. The key idea behind CAD is to shift the point of durability from writes to reads. By delaying durability upon writes, CAD provides high performance; however, by ensuring the durability of data before serving reads, CAD enables the construction of strong consistency models. Finally, we introduce cross-client monotonic reads, a novel and strong consistency property that provides monotonic reads across failures and sessions. We show that this property can be efficiently realized upon CAD, while other durability models cannot enable this property with high performance. We also demonstrate the benefits of this new consistency model.