按年被提到
20222022 · 1 次2026
系统、数据库与网络›分布式数据与 CRDT·arXiv:2205.12425 · cs.PL

Katara: Synthesizing CRDTs with Verified Lifting

Shadaj Laddad, Conor Power, Mae Milano, Alvin Cheung, Joseph M. Hellerstein · 2022
开始阅读 ↗PDFalphaXiv 讨论
被提及 · 2 人首次 2022-09-26 · 最近 2023-09-04
2不同的人
2活跃月份
2讨论串
1被引(OpenAlex)
arXiv 摘要(候选层不写导读)

Conflict-free replicated data types (CRDTs) are a promising tool for designing scalable, coordination-free distributed systems. However, constructing correct CRDTs is difficult, posing a challenge for even seasoned developers. As a result, CRDT development is still largely the domain of academics, with new designs often awaiting peer review and a manual proof of correctness. In this paper, we present Katara, a program synthesis-based system that takes sequential data type implementations and automatically synthesizes verified CRDT designs from them. Key to this process is a new formal definition of CRDT correctness that combines a reference sequential type with a lightweight ordering constraint that resolves conflicts between non-commutative operations. Our process follows the tradition of work in verified lifting, including an encoding of correctness into SMT logic using synthesized inductive invariants and hand-crafted grammars for the CRDT state and runtime. Katara is able to automatically synthesize CRDTs for a wide variety of scenarios, from reproducing classic CRDTs to synthesizing novel designs based on specifications in existing literature. Crucially, our synthesized CRDTs are fully, automatically verified, eliminating entire classes of common errors and reducing the process of producing a new CRDT from a painstaking paper proof of correctness to a lightweight specification.

候选层:至少 2 个不同的人、在 2 个不同月份提到过,还没到主书架的 3 人 3 个月。没有做立场标注,所以只写“被提及”。

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
评论refset · 2023-09

“CRDT synthesis feels like a promising direction, e.g. see "Katara: Synthesizing CRDTs with Verified Lifting"/ https://arxiv.org/abs/2205.12425 / previous discussion https://news.ycombinator.com/item?id=32977887”

Cola: A text CRDT for real-time collaborative editing原评论 ↗
被提交为 story · 1 次