RunTime-assisted convergence in replicated data types
Gowtham Kaki, Prasanth Prahladan, and Nicholas V. Lewchenko
PLDI 2022: ACM SIGPLAN Conference on Programming Language Design and Implementation


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.


@string{PLDI = "ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI)"}
  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},