Reference
Abstract
We propose a runtime-assisted approach to enforce convergence in distributed executions of replicated data types. The key distinguishing aspect of our approach is that it guarantees convergence unconditionally – without requiring data type operations to satisfy algebraic laws such as commutativity and idempotence. Consequently, programmers are no longer obligated to prove convergence on a per-type basis. Moreover, our approach lets sequential data types be reused in a distributed setting by extending their implementations rather than refactoring them. The novel component of our approach is a distributed runtime that orchestrates well-formed executions that are guaranteed to converge. Despite the utilization of a runtime, our approach comes at no additional cost of latency and availability. Instead, we introduce a novel tradeoff against a metric called staleness, which roughly corresponds to the time taken for replicas to converge. We implement our approach in a system called Quark and conduct a thorough evaluation of its tradeoffs.
BibTeX
@string{PLDI = "ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI)"}
@inproceedings{runtimeassisted-pldi22,
author = {Gowtham Kaki and Prasanth Prahladan and Nicholas V. Lewchenko},
title = {RunTime-assisted convergence in replicated data types},
booktitle = PLDI,
year = {2022},
pages = {364-378},
}