Memory Access Efficiency in Distributed Atomic Object Implementations

Distributed data services use redundancy to ensure data availability and survivability. Replication can be used to mask failures, however it introduces the problem of consistency because operations may access different object replicas, possibly containing obsolete values. Atomicity is a venerable notion of consistency, introduced in 1979 by Lamport. Atomicity is the most natural type of consistency because it provides an illusion of equivalence with the serial object type that software designers expect. We deal with the storage of atomic shared readable and writable data in distributed systems that are subject to perturbations in the underlying distributed platforms composed of computers and networks that interconnect them. The perturbations may include permanent crashes of individual computers, transient failures, and delays in the communication medium. The contents of each object are replicated across several replica servers and clients invoke read/write operations on the objects. A new approach that exploits server-to-server communication is introduced. We devise a solution for the Single-Writer, Multiple-Reader setting where operations do not necessarily need to involve complete round-trips between clients and servers, i.e., operations take “one-and-a-half-rounds”. We extend the SWMR solution to yield an algorithm for the Multiple-Writer, Multiple-Reader setting. Next, we investigate implementations that reduce both communication and computation demands and we devise two SWMR algorithms. Lastly, we devise algorithms for both SWMR and MWMR settings where reads can take at most one-and-a-half-rounds, in a system with unconstrained quorum construction and reader participation. Algorithms have provable performance and correctness guarantees. Empirical studies are performed on the proposed algorithms