Nowadays the traditional file systems cannot handle the new requirements in terms of volume of data, high performance, fault-tolerance, and improved capabilities. So Distributed Storage Systems (DSS) took place to cover the need of a shared storage between separate systems, provide a scalable storage to serve thousands of servers, and improve the fault-tolerance. To this respect, a series of issues need to be properly addressed: scalability, the ability to handle large data, high performance even under heavy access concurrency, versioning, and fault-tolerance. In this work, we propose CoBFS , a framework of a DSS designed to boost the concurrent access to large shared data objects (such as files), while maintaining strong consistency guarantees. CoBFS has two key design factors: data striping and versioning-based concurrency control (through coverability) to enable higher operation performance on large concurrent data objects. To this respect, we introduce the notions of a block as a “bounded” Read/Write register, of a fragmented object as a sequence of blocks, and of fragmented coverable linearizability , a strong consistency property suitable for fragmented objects. CoBFS adopts a modular architecture, separating the object fragmentation process from the shared memory service allowing to use different shared memory implementations. At first, we use as storage a static atomic distributed shared memory (ADSM) emulation, the well known ABD , yielding CoABDF , which satisfies fragmented coverable linearizability. Then, we substitute the storage layer of CoBFS with a dynamic (reconfigurable) storage algorithm, called Ares , yielding CoAresF ; CoAresF allows the addition and removal of servers without system interruptions and improves the storage efficiency due to the use of an erasure-coded mechanism. We conduct an extensive experimental evaluation on the Emulab and AWS EC2 testbeds, illustrating the benefits of our approaches, as well as other interesting tradeoffs. We believe that CoBFS ’s features (versioning, high concurrent accesses, handling large objects) has the potential of benefiting any static or dynamic storage algorithm to further extend its functionality for data-intensive applications at large scale.

Reading, 'Riting, and 'Rithmetic, the three R's underlying much of human intellectual activity, not surprisingly, also stand as a venerable foundation of modern computing technology. Indeed, both the Turing machine and von Neumann machine models operate by reading, writing, and computing, and all practical uniprocessor implementations are based on performing activities structured in terms of the three R's. With the advance of networking technology, communication became an additional major systemic activity. However, at a high level of abstraction, it is apparently still more natural to think in terms of reading, writing, and computing. While it is hard to imagine distributed systems - such as those implementing the World-Wide Web - without communication, we often imagine browser-based applications that operate by retrieving (i.e., reading) data, performing computation, and storing (i.e., writing) the results. In this article, we deal with the storage of 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 failures (or crashes) of individual computers, transient failures, and delays in the communication medium. The focus of this paper is on the implementations of distributed atomic memory services. Atomicity is a venerable notion of consistency, introduced in 1979 by Lamport [Lamport, 1979]. To this day atomicity remains the most natural type of consistency because it provides an illusion of equivalence with the serial object type that software designers expect. We define the overall setting, models of computation, definition of atomic consistency, and measures of efficiency. We then present algorithms for single-writer settings in the static models. Then we move to presenting algorithms for multi-writer settings. For both static settings we discuss design issues, correctness, efficiency, and trade-offs. Lastly we survey the implementation issues in dynamic settings, where the universe of participants may completely change over time. Here the expectation is that solutions are found by integrating static algorithms with a reconfiguration framework so that during periods of relative stability one benefits from the efficiency of static algorithms, and where during the more turbulent times performance degrades gracefully when reconfigurations are needed. We describe the most important approaches and provide examples.

Communication demands are usually the leading factor that defines the efficiency of operations on a read/write shared memory emulation in the message-passing environment. In the quest for minimizing the communication demands, the algorithms proposed either require restrictions in the system or incur high computation demands. As a result, such solutions may be not suitable to be used in practice. In this paper we focus on the practicality of implementations of atomic read/write shared memory emulation in the message-passing environment. In particular we investigate implementations that reduce both communication and computation demands. We first examine the shortcomings of the best two (in terms of communication demands) known algorithms that implement atomic single-writer multiple-reader (SWMR) atomic memory. The algorithm ccFast proposed by A. Fernández et al., achieves optimal communication by allowing each operation to complete in one round trip, with light computation requirements. Unfortunately, it relies on strict limitations on the number of readers. On the other hand, algorithm OhSam, imposes no restrictions on the system, but provides operations that require one and a half communication rounds. In the light of these shortcomings, we present two algorithms that implement multi-speed operations with light computation, and without imposing any restriction on the system. In particular, algorithm ccHybrid adopts the fast (one-round) writes and makes clients to switch to a slow (two-round) mode whenever the system is congested. On the other hand, algorithm OhFast, pushes the responsibility of deciding for the speed switch to the servers. This allows the algorithm to utilize the fast operations, and the slow one-and-a-half-rounds operations of the algorithm presented by T. Hadjistasi et al., whenever is necessary. We prove that both new algorithms preserve atomicity. To evaluate the new algorithms we implement five different atomic memory algorithms in the NS3 simulator, and we compare their performance in terms of operation latency, and ratio of slow over fast operations performed. We test the algorithms over different: (i) topologies, and (ii) operation loads. Our results support that the newly presented algorithms increase the practicality of atomic read/write atomic shared memory implementations in the message-passing, asynchronous environment.

Emulating atomic read/write shared objects in a message-passing system is a fundamental problem in distributed computing. Considering that network communication is the most expensive resource, efficiency is measured first of all in terms of the communication needed to implement read and write operations. It is well known that two communication round-trip phases involving in total four message exchanges are sufficient to implemented atomic operations. In this work we present a comprehensive treatment of the question of when and how it is possible to implement atomic memory where read and write operations complete in three message exchanges, i.e., we aim for One and half Round Atomic Memory, hence the name Oh-RAM! We present algorithms that allow operations to complete in three communication exchanges without imposing any constraints on the number of readers and writers. We present an implementation for the {single-writer/multiple-reader} (SWMR) setting, where reads complete in three communication exchanges and writes complete in two exchanges. Then we pose the question of whether it is possible to implement multiple-writer/multiple-reader (MWMR) memory where operations complete in at most three communication exchanges. In light of our impossibility result these algorithms are optimal in terms of the number of communication exchanges.