Search for: All records

Shared register emulations on top of message- passing systems provide an illusion of a simpler shared memory system which can make the task of a system designer easier. Numerous shared register applications have a considerably high read to write ratio. Thus having algorithms that make reads more efficient than writes is a fair trade-off. Typically such algorithms for reads and writes are asymmetric and sacrifice the stringent consistency condition atomicity as it is impossible to have fast reads for multi-writer atomicity. Safety is a consistency condition has has gathered interest from both the systems and theory community as it is weaker than atomicity yet provides strong enough guarantees like “strong consistency” or read-my-write consistency. One requirement that is assumed by many researchers is that of the reliable broadcast (RB) primitive, which ensures the all or none property during a broadcast. One drawback is that such a primitive takes 1.5 rounds to complete. This paper implements an efficient multi-writer multi-reader safe register without using a reliable broadcast primitive. More- over, we provide fast reads or one-shot reads – our read operation can be completed in one round of client-to-server communication. Of course, this comes with the price of requiring more servers when compared to prior solutions assuming reliable broadcast. However, we show that this increased number of servers is indeed necessary as we prove a tight bound on the number of servers required to implement Byzantine-fault tolerant safe registers in a system without reliable broadcast. We extend our results to data stored using erasure coding as well. We present an emulation of single-writer multi-reader safe register based on MDS code. The usage of MDS code reduces storage cost and communication cost. On the negative side, we also show that to use MDS code and achieve one-shot read at the same time, we need even more servers. 

Collaborative text editing applications like Google docs, Etherpad and Overleaf allow users to con- currently edit a “shared” document. Most existing collab- orative text editing software require total ordering on the updates made to the document, which is achieved using a centralized sever or some form of consensus algorithm. Then on top of the ordering, the editor uses either opera- tional transformation (OT) or differential synchronization (diff-sync) to apply the ordered update events to the already committed changes on their local copies. If there is no delay or failure, then eventually all updates can be applied correctly in the agreed order. Unfortunately, not only are these methods computation- ally intensive but they often result in conflicts due to users writing to the same location. It has also been proved that the metadata overhead for such protocols are at least linear in the number of delete events. Moreover, these event- based and diff-based algorithms are exceptionally difficult to implement and there are no provably correct solutions to these problems in the face of heavy concurrency. These collaborative editors either provide no proven guarantees or only provide eventual guarantees for correctness. With LiteDoc, we propose a different approach to tackle this problem: we make collaborative editing fast, scalable and robust by providing simplified semantics. More im- portantly, we can formally prove that LiteDoc achieves deterministic guarantees of correctness. LiteDoc divides the shared document into several sections and allow only one user to write at a particular section at any given time. This removes all conflicts that arise from having multiple writers writing to the same location. This mechanism also obviates the task of implementing cumbersome modules for OT, diff-sync and rollbacks in case of conflicts. Note that while LiteDoc supports less features than general collaborative editors like Google docs, it is natural (and courteous) to avoid concurrent writing to the same location when multiple people collaborate. 

We study distributed causal shared memory (or key- value pairs) in an asynchronous network under crash failures. Causal memory, introduced by Ahamad et al. in the context of multi-processor environment in 1994, is an abstraction which ensures that nodes agree on the relative ordering of read and write operations that are causally related on key-value pairs. Inspired by the recent interests in geo-replicated causal storage systems (e.g., COPS, Eiger, Bolt-on), we systematically study the fault-tolerance property of the causal shared memory in the client-server model in this work. We identify that 2f + 1 servers is both necessary and sufficient to build a resilient causal memory in the presence of up to f crashed servers. We provide both the necessity proof and a new optimal algorithm that matches the bound. For evaluation, we implement our algorithm in Golang and compare the perfor- mance with state-of-the-art fault-tolerant algorithms that ensure atomicity in the Google Cloud Platform.